#[cfg(test)]
use std::cell::Cell;
use std::cell::RefCell;
use std::mem::{MaybeUninit, size_of};
use std::ops::Deref;
use std::ptr::NonNull;
use std::sync::Arc;
use std::sync::atomic::fence;
use std::sync::atomic::{AtomicBool, AtomicPtr, AtomicU8, AtomicU64, AtomicUsize, Ordering};
use crossbeam_epoch::{Atomic, Collector, Guard, LocalHandle, Owned, Shared, unprotected};
use crate::InvariantError;
use crate::config::SIZE_CLASSES;
use crate::os::{release_metadata_block, reserve_commit_metadata_block};
use crate::payload_vec::{PayloadVec, PayloadVecSlabOwner};
use crate::span::{SpanDesc, SpanHandle, SpanKind, SpanSlabOwner};
pub(crate) const FANOUT: usize = 64;
type NodeId = usize;
type LeafEntries = PayloadVec<(usize, SpanHandle), { FANOUT + 2 }, 1152>;
type InternalKeys = PayloadVec<usize, { FANOUT + 2 }, 640>;
type InternalChildren = PayloadVec<NodeId, { FANOUT + 3 }, 640>;
type FreeFitScore = (usize, usize, usize);
type ScoredFreeFit = (SpanHandle, usize, FreeFitScore);
const NO_NODE: usize = usize::MAX;
const NODE_SEGMENT_SIZE: usize = 256;
const MAX_NODE_SEGMENTS: usize = 4096;
const NODE_SEGMENT_BYTES: usize = 4096;
const NODE_RECORD_BYTES: usize = 16;
const NODE_ARENA_SEGMENT_BYTES: usize = NODE_SEGMENT_BYTES + NODE_SEGMENT_SIZE * NODE_RECORD_BYTES;
const METADATA_BLOCK_BYTES: usize = 64 * 1024;
const SEGMENTS_PER_METADATA_BLOCK: usize = METADATA_BLOCK_BYTES / NODE_ARENA_SEGMENT_BYTES;
const MAX_METADATA_BLOCKS: usize = MAX_NODE_SEGMENTS.div_ceil(SEGMENTS_PER_METADATA_BLOCK);
const TREE_NODE_SLOT_BYTES: usize = 128;
const TREE_NODES_PER_METADATA_BLOCK: usize = METADATA_BLOCK_BYTES / TREE_NODE_SLOT_BYTES;
const MAX_TREE_NODE_BLOCKS: usize =
(MAX_NODE_SEGMENTS * NODE_SEGMENT_SIZE).div_ceil(TREE_NODES_PER_METADATA_BLOCK);
const SEGMENT_INITIALIZING: *mut NodeSegment = std::ptr::dangling_mut::<NodeSegment>();
const FREE_NODE_NONE: usize = 0;
const FREE_NODE_INDEX_BITS: u32 = 21;
const FREE_NODE_INDEX_MASK: u64 = (1_u64 << FREE_NODE_INDEX_BITS) - 1;
const OP_INIT: u8 = 0;
const OP_FROZEN: u8 = 1;
const OP_LINKED: u8 = 2;
const OP_PARENTED: u8 = 3;
const OP_DONE: u8 = 4;
const OP_ABORTED: u8 = 5;
const VERSION_OPERATION_FROZEN: u64 = 1 << 63;
const CANDIDATE_CREATING: usize = 1 << (usize::BITS - 1);
static NEXT_TREE_EPOCH_ID: AtomicUsize = AtomicUsize::new(1);
#[cfg(test)]
static NEXT_PAYLOAD_ID: AtomicU64 = AtomicU64::new(1);
type TreeEpochHandles = RefCell<Vec<(usize, Box<LocalHandle>)>>;
fn new_tree_epoch_handles() -> TreeEpochHandles {
RefCell::new(Vec::new())
}
static TREE_EPOCH_HANDLES: crate::tls::NativeThreadLocal<TreeEpochHandles> =
crate::tls::NativeThreadLocal::new(new_tree_epoch_handles);
#[cfg(test)]
thread_local! {
static PAUSE_REDISTRIBUTION_AFTER_PUBLISH: Cell<bool> = const { Cell::new(false) };
static PAUSE_RIGHT_REDIRECT_BEFORE_SPLICE: Cell<bool> = const { Cell::new(false) };
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct ChunkRecord {
pub base: usize,
pub size: usize,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct LocalityHint {
pub address: usize,
pub chunk_base: usize,
}
pub(crate) struct TopologyReadSnapshot {
class_spans: Vec<Box<[SpanHandle]>>,
run_spans: Box<[SpanHandle]>,
dedicated_spans: Box<[SpanHandle]>,
}
impl TopologyReadSnapshot {
pub fn empty() -> Self {
Self {
class_spans: (0..SIZE_CLASSES.len())
.map(|_| Vec::new().into_boxed_slice())
.collect(),
run_spans: Box::new([]),
dedicated_spans: Box::new([]),
}
}
pub fn from_topology(topology: &Topology) -> Self {
Self::from_tree(&topology.tree)
}
pub fn from_tree(tree: &AddressTree) -> Self {
let mut class_spans: Vec<Vec<SpanHandle>> =
(0..SIZE_CLASSES.len()).map(|_| Vec::new()).collect();
let mut run_spans = Vec::new();
let mut dedicated_spans = Vec::new();
for span in tree.values() {
match span.kind() {
SpanKind::Small | SpanKind::ReservedSmall => {
if let Some(class_index) = span.class_index() {
class_spans[class_index].push(span);
}
}
SpanKind::Run | SpanKind::ReservedRun => run_spans.push(span),
SpanKind::Dedicated | SpanKind::DedicatedReserved => dedicated_spans.push(span),
SpanKind::Free | SpanKind::Retired => {}
}
}
Self {
class_spans: class_spans.into_iter().map(Vec::into_boxed_slice).collect(),
run_spans: run_spans.into_boxed_slice(),
dedicated_spans: dedicated_spans.into_boxed_slice(),
}
}
pub fn class_spans(&self, class_index: usize) -> &[SpanHandle] {
&self.class_spans[class_index]
}
pub fn run_spans(&self, dedicated: bool) -> &[SpanHandle] {
if dedicated {
&self.dedicated_spans
} else {
&self.run_spans
}
}
}
#[repr(align(64))]
struct TreeNode {
parent: AtomicUsize,
right_sibling: AtomicUsize,
high_key: AtomicUsize,
version: AtomicU64,
operation: Atomic<OperationDescriptor>,
data: Atomic<NodePayload>,
payload_slabs: AtomicPtr<PayloadSlabs>,
}
trait IntoTreeNode {
fn into_tree_node(self) -> TreeNode;
}
impl IntoTreeNode for TreeNode {
fn into_tree_node(self) -> TreeNode {
self
}
}
#[cfg(test)]
impl IntoTreeNode for Arc<TreeNode> {
fn into_tree_node(self) -> TreeNode {
match Arc::try_unwrap(self) {
Ok(node) => node,
Err(_) => panic!("test TreeNode Arc escaped before slab insertion"),
}
}
}
struct OperationDescriptor {
phase: AtomicU8,
payload_replaced: AtomicU8,
replacement_data: AtomicUsize,
replacement_high: usize,
kind: OperationKind,
}
enum OperationKind {
RootReplace {
left_id: NodeId,
right_id: NodeId,
root_id: NodeId,
},
RootCollapse {
expected_version: u64,
expected_data: usize,
child_id: NodeId,
},
LeafSplit {
expected_version: u64,
expected_data: usize,
old_right: NodeId,
old_high: usize,
separator: usize,
right_id: AtomicUsize,
root_id: AtomicUsize,
needs_root: bool,
left_data: NodeData,
right_data: NodeData,
},
ParentInsert {
expected_version: u64,
expected_data: usize,
right_id: NodeId,
new_data: NodeData,
},
InternalSplit {
expected_version: u64,
expected_data: usize,
old_right: NodeId,
old_high: usize,
separator: usize,
right_id: AtomicUsize,
root_id: AtomicUsize,
needs_root: bool,
left_data: NodeData,
right_data: NodeData,
moved_children: Box<[NodeId]>,
},
LogicalRemove {
expected_version: u64,
expected_data: usize,
new_data: NodeData,
},
LeafUpsert {
expected_version: u64,
expected_data: usize,
new_data: NodeData,
},
Redirect {
expected_version: u64,
expected_data: usize,
target: NodeId,
},
LeftRedirect {
source_id: NodeId,
expected_version: u64,
expected_data: usize,
left_id: NodeId,
left_expected_version: u64,
left_expected_data: usize,
left_old_high: usize,
left_new_high: usize,
left_data: Option<NodeData>,
left_replacement_data: AtomicUsize,
moved_children: Box<[NodeId]>,
parent_id: NodeId,
parent_expected_version: u64,
parent_expected_data: usize,
parent_high: usize,
parent_data: NodeData,
parent_replacement_data: AtomicUsize,
right_id: NodeId,
},
RightRedirect {
source_id: NodeId,
expected_version: u64,
expected_data: usize,
right_id: NodeId,
right_expected_version: u64,
right_expected_data: usize,
right_high: usize,
right_data: NodeData,
right_replacement_data: AtomicUsize,
moved_children: Box<[NodeId]>,
parent_id: NodeId,
parent_expected_version: u64,
parent_expected_data: usize,
parent_high: usize,
parent_data: NodeData,
parent_replacement_data: AtomicUsize,
},
InternalRedistribute {
source_id: NodeId,
expected_version: u64,
expected_data: usize,
old_source_high: usize,
new_source_high: usize,
source_data: NodeData,
sibling_id: NodeId,
sibling_expected_version: u64,
sibling_expected_data: usize,
old_sibling_high: usize,
new_sibling_high: usize,
sibling_data: NodeData,
sibling_replacement_data: AtomicUsize,
moved_children: Box<[NodeId]>,
parent_id: NodeId,
parent_expected_version: u64,
parent_expected_data: usize,
parent_high: usize,
parent_data: NodeData,
parent_replacement_data: AtomicUsize,
},
}
#[derive(Clone)]
enum NodeData {
Leaf {
entries: LeafEntries,
},
Internal {
keys: InternalKeys,
children: InternalChildren,
},
Redirect {
target: NodeId,
},
}
struct NodePayload {
high_key: usize,
data: NodeData,
#[cfg(test)]
debug_id: u64,
#[cfg(test)]
debug_origin: &'static str,
#[cfg(test)]
debug_created_high: usize,
#[cfg(test)]
debug_created_last: Option<usize>,
}
impl NodePayload {
fn new(high_key: usize, data: NodeData, _origin: &'static str) -> Self {
#[cfg(test)]
assert_payload_fence(&data, high_key, _origin);
Self {
high_key,
#[cfg(test)]
debug_id: NEXT_PAYLOAD_ID.fetch_add(1, Ordering::Relaxed),
#[cfg(test)]
debug_origin: _origin,
#[cfg(test)]
debug_created_high: high_key,
#[cfg(test)]
debug_created_last: match &data {
NodeData::Leaf { entries } => entries.last().map(|entry| entry.0),
NodeData::Internal { keys, .. } => keys.last().copied(),
NodeData::Redirect { .. } => None,
},
data,
}
}
fn freeze(mut self, slabs: &PayloadSlabs) -> Self {
self.data = match self.data {
NodeData::Leaf { entries } => NodeData::Leaf {
entries: entries.freeze(&slabs.leaf_entries),
},
NodeData::Internal { keys, children } => NodeData::Internal {
keys: keys.freeze(&slabs.internal_keys),
children: children.freeze(&slabs.internal_children),
},
redirect @ NodeData::Redirect { .. } => redirect,
};
debug_assert!(match &self.data {
NodeData::Leaf { entries } => entries.is_frozen(),
NodeData::Internal { keys, children } => keys.is_frozen() && children.is_frozen(),
NodeData::Redirect { .. } => true,
});
self
}
}
struct PayloadSlabs {
leaf_entries: PayloadVecSlabOwner<(usize, SpanHandle), { FANOUT + 2 }, 1152>,
internal_keys: PayloadVecSlabOwner<usize, { FANOUT + 2 }, 640>,
internal_children: PayloadVecSlabOwner<NodeId, { FANOUT + 3 }, 640>,
}
impl PayloadSlabs {
fn new() -> Self {
Self {
leaf_entries: PayloadVecSlabOwner::new(),
internal_keys: PayloadVecSlabOwner::new(),
internal_children: PayloadVecSlabOwner::new(),
}
}
fn slots(&self) -> usize {
self.leaf_entries.slots() + self.internal_keys.slots() + self.internal_children.slots()
}
fn live(&self) -> usize {
self.leaf_entries.live() + self.internal_keys.live() + self.internal_children.live()
}
fn reused(&self) -> u64 {
self.leaf_entries.reused() + self.internal_keys.reused() + self.internal_children.reused()
}
fn allocated_blocks(&self) -> usize {
self.leaf_entries.allocated_blocks()
+ self.internal_keys.allocated_blocks()
+ self.internal_children.allocated_blocks()
}
fn control_bytes(&self) -> usize {
self.leaf_entries.control_bytes()
+ self.internal_keys.control_bytes()
+ self.internal_children.control_bytes()
}
}
#[cfg(test)]
fn assert_payload_fence(data: &NodeData, high_key: usize, context: &str) {
let keys = match data {
NodeData::Leaf { entries } => entries.iter().map(|entry| entry.0).collect::<Vec<_>>(),
NodeData::Internal { keys, .. } => keys.to_vec(),
NodeData::Redirect { .. } => Vec::new(),
};
assert!(
keys.windows(2).all(|window| window[0] < window[1]),
"{context} publishes unordered keys"
);
let last_key = keys.last().copied();
assert!(
last_key.is_none_or(|key| key < high_key),
"{context} publishes key {last_key:#x?} beyond fence {high_key:#x}"
);
}
#[repr(C, align(64))]
struct TreeNodeSlot {
references: AtomicUsize,
next_free: AtomicUsize,
index: usize,
slab: NonNull<TreeNodeSlab>,
node: MaybeUninit<TreeNode>,
}
const _: () = assert!(size_of::<TreeNode>() == 64);
const _: () = assert!(size_of::<TreeNodeSlot>() == TREE_NODE_SLOT_BYTES);
struct TreeNodeSlab {
blocks: [AtomicUsize; MAX_TREE_NODE_BLOCKS],
lifetime_references: AtomicUsize,
next: AtomicUsize,
free_head: AtomicU64,
live: AtomicUsize,
reused: AtomicU64,
}
impl TreeNodeSlab {
fn new() -> Self {
Self {
blocks: std::array::from_fn(|_| AtomicUsize::new(0)),
lifetime_references: AtomicUsize::new(1),
next: AtomicUsize::new(0),
free_head: AtomicU64::new(0),
live: AtomicUsize::new(0),
reused: AtomicU64::new(0),
}
}
fn block(&self, block_index: usize) -> usize {
let current = self.blocks[block_index].load(Ordering::Acquire);
if current != 0 {
return current;
}
let candidate = unsafe { reserve_commit_metadata_block(METADATA_BLOCK_BYTES) }
.unwrap_or_else(|error| panic!("unable to reserve TreeNode metadata block: {error}"));
for offset in 0..TREE_NODES_PER_METADATA_BLOCK {
let slot = (candidate + offset * TREE_NODE_SLOT_BYTES) as *mut TreeNodeSlot;
unsafe {
slot.write(TreeNodeSlot {
references: AtomicUsize::new(0),
next_free: AtomicUsize::new(FREE_NODE_NONE),
index: block_index * TREE_NODES_PER_METADATA_BLOCK + offset,
slab: NonNull::from(self),
node: MaybeUninit::uninit(),
})
};
}
match self.blocks[block_index].compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
let _ = unsafe { release_metadata_block(candidate) };
installed
}
}
}
fn slot(&self, index: usize) -> &TreeNodeSlot {
let block_index = index / TREE_NODES_PER_METADATA_BLOCK;
assert!(
block_index < MAX_TREE_NODE_BLOCKS,
"TreeNode metadata slab exhausted"
);
let block = self.block(block_index);
let offset = index % TREE_NODES_PER_METADATA_BLOCK;
unsafe { &*((block + offset * TREE_NODE_SLOT_BYTES) as *const TreeNodeSlot) }
}
fn pop_free(&self) -> Option<usize> {
let mut head = self.free_head.load(Ordering::Acquire);
loop {
let encoded = (head & FREE_NODE_INDEX_MASK) as usize;
if encoded == FREE_NODE_NONE {
return None;
}
let index = encoded - 1;
let next = self.slot(index).next_free.load(Ordering::Acquire);
let tag = (head >> FREE_NODE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << FREE_NODE_INDEX_BITS) | next as u64;
match self.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(index),
Err(actual) => head = actual,
}
}
}
fn push_free(&self, index: usize) {
let encoded = index.checked_add(1).expect("TreeNode slab index overflow");
assert!(encoded <= FREE_NODE_INDEX_MASK as usize);
let slot = self.slot(index);
let mut head = self.free_head.load(Ordering::Acquire);
loop {
slot.next_free
.store((head & FREE_NODE_INDEX_MASK) as usize, Ordering::Release);
let tag = (head >> FREE_NODE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << FREE_NODE_INDEX_BITS) | encoded as u64;
match self.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return,
Err(actual) => head = actual,
}
}
}
fn allocate(&self, node: TreeNode) -> NodeHandle {
let reused = self.pop_free();
let index = reused.unwrap_or_else(|| self.next.fetch_add(1, Ordering::AcqRel));
let slot = self.slot(index);
assert_eq!(slot.references.load(Ordering::Acquire), 0);
unsafe { (slot.node.as_ptr() as *mut TreeNode).write(node) };
let lifetime = self.lifetime_references.fetch_add(1, Ordering::Relaxed);
assert!(lifetime != 0 && lifetime < usize::MAX / 2);
slot.references.store(1, Ordering::Release);
self.live.fetch_add(1, Ordering::Relaxed);
if reused.is_some() {
self.reused.fetch_add(1, Ordering::Relaxed);
}
NodeHandle {
slot: NonNull::from(slot),
}
}
fn allocated_blocks(&self) -> usize {
self.blocks
.iter()
.filter(|block| block.load(Ordering::Acquire) != 0)
.count()
}
unsafe fn release_lifetime(slab: NonNull<Self>) {
let slab_ref = unsafe { slab.as_ref() };
if slab_ref.lifetime_references.fetch_sub(1, Ordering::Release) != 1 {
return;
}
fence(Ordering::Acquire);
unsafe { drop(Box::from_raw(slab.as_ptr())) };
}
}
impl Drop for TreeNodeSlab {
fn drop(&mut self) {
debug_assert_eq!(self.live.load(Ordering::Relaxed), 0);
for block in &self.blocks {
let address = block.load(Ordering::Relaxed);
if address != 0 {
let _ = unsafe { release_metadata_block(address) };
}
}
}
}
struct TreeNodeSlabOwner {
slab: NonNull<TreeNodeSlab>,
}
unsafe impl Send for TreeNodeSlabOwner {}
unsafe impl Sync for TreeNodeSlabOwner {}
impl TreeNodeSlabOwner {
fn new() -> Self {
let slab = Box::new(TreeNodeSlab::new());
Self {
slab: unsafe { NonNull::new_unchecked(Box::into_raw(slab)) },
}
}
}
impl Deref for TreeNodeSlabOwner {
type Target = TreeNodeSlab;
fn deref(&self) -> &Self::Target {
unsafe { self.slab.as_ref() }
}
}
impl Drop for TreeNodeSlabOwner {
fn drop(&mut self) {
unsafe { TreeNodeSlab::release_lifetime(self.slab) };
}
}
struct NodeHandle {
slot: NonNull<TreeNodeSlot>,
}
unsafe impl Send for NodeHandle {}
unsafe impl Sync for NodeHandle {}
impl Clone for NodeHandle {
fn clone(&self) -> Self {
let slot = unsafe { self.slot.as_ref() };
let previous = slot.references.fetch_add(1, Ordering::Relaxed);
assert!(previous != 0 && previous < usize::MAX / 2);
Self { slot: self.slot }
}
}
impl Deref for NodeHandle {
type Target = TreeNode;
fn deref(&self) -> &Self::Target {
let slot = unsafe { self.slot.as_ref() };
unsafe { &*slot.node.as_ptr() }
}
}
impl Drop for NodeHandle {
fn drop(&mut self) {
let slot = unsafe { self.slot.as_ref() };
if slot.references.fetch_sub(1, Ordering::Release) != 1 {
return;
}
fence(Ordering::Acquire);
unsafe { std::ptr::drop_in_place(slot.node.as_ptr() as *mut TreeNode) };
let slab = unsafe { slot.slab.as_ref() };
slab.live.fetch_sub(1, Ordering::Relaxed);
slab.push_free(slot.index);
unsafe { TreeNodeSlab::release_lifetime(slot.slab) };
}
}
struct NodeRecord {
node: NodeHandle,
retirement_scheduled: AtomicBool,
}
const _: () = assert!(size_of::<NodeRecord>() <= NODE_RECORD_BYTES);
struct NodeSlot {
record: Atomic<NodeRecord>,
next_free: AtomicUsize,
}
impl NodeSlot {
fn new() -> Self {
Self {
record: Atomic::null(),
next_free: AtomicUsize::new(FREE_NODE_NONE),
}
}
}
#[repr(C, align(64))]
struct NodeSegment {
slots: [NodeSlot; NODE_SEGMENT_SIZE],
}
const _: () = assert!(size_of::<NodeSegment>() == NODE_SEGMENT_BYTES);
impl NodeSegment {
fn new() -> Self {
Self {
slots: std::array::from_fn(|_| NodeSlot::new()),
}
}
}
struct NodeArena {
segments: [AtomicPtr<NodeSegment>; MAX_NODE_SEGMENTS],
metadata_blocks: [AtomicUsize; MAX_METADATA_BLOCKS],
payloads: PayloadSlabs,
node_slab: TreeNodeSlabOwner,
next: AtomicUsize,
free_head: AtomicU64,
live: AtomicUsize,
retired: AtomicU64,
reused: AtomicU64,
}
impl NodeArena {
fn new() -> Self {
Self {
segments: std::array::from_fn(|_| AtomicPtr::new(std::ptr::null_mut())),
metadata_blocks: std::array::from_fn(|_| AtomicUsize::new(0)),
payloads: PayloadSlabs::new(),
node_slab: TreeNodeSlabOwner::new(),
next: AtomicUsize::new(0),
free_head: AtomicU64::new(0),
live: AtomicUsize::new(0),
retired: AtomicU64::new(0),
reused: AtomicU64::new(0),
}
}
fn metadata_block(&self, index: usize) -> Result<usize, crate::BoAllocError> {
let current = self.metadata_blocks[index].load(Ordering::Acquire);
if current != 0 {
return Ok(current);
}
let candidate = unsafe { reserve_commit_metadata_block(METADATA_BLOCK_BYTES)? };
match self.metadata_blocks[index].compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => Ok(candidate),
Err(installed) => {
unsafe { release_metadata_block(candidate)? };
Ok(installed)
}
}
}
fn segment(&self, index: usize) -> *mut NodeSegment {
loop {
let current = self.segments[index].load(Ordering::Acquire);
if current == SEGMENT_INITIALIZING {
std::hint::spin_loop();
continue;
}
if !current.is_null() {
return current;
}
if self.segments[index]
.compare_exchange(
std::ptr::null_mut(),
SEGMENT_INITIALIZING,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_err()
{
continue;
}
let block_index = index / SEGMENTS_PER_METADATA_BLOCK;
let block = match self.metadata_block(block_index) {
Ok(block) => block,
Err(error) => {
self.segments[index].store(std::ptr::null_mut(), Ordering::Release);
panic!("unable to reserve B+ metadata block: {error}")
}
};
let offset = (index % SEGMENTS_PER_METADATA_BLOCK) * NODE_ARENA_SEGMENT_BYTES;
let segment = (block + offset) as *mut NodeSegment;
unsafe { segment.write(NodeSegment::new()) };
self.segments[index].store(segment, Ordering::Release);
return segment;
}
}
fn published_segment(&self, index: usize) -> *mut NodeSegment {
loop {
let segment = self.segments[index].load(Ordering::Acquire);
if segment != SEGMENT_INITIALIZING {
return segment;
}
std::hint::spin_loop();
}
}
fn record_storage(segment: *mut NodeSegment, slot_index: usize) -> *mut NodeRecord {
debug_assert!(slot_index < NODE_SEGMENT_SIZE);
(segment as usize + NODE_SEGMENT_BYTES + slot_index * NODE_RECORD_BYTES) as *mut NodeRecord
}
fn slot(&self, id: NodeId) -> Option<&NodeSlot> {
if id >= self.next.load(Ordering::Acquire) {
return None;
}
let segment = self.published_segment(id / NODE_SEGMENT_SIZE);
if segment.is_null() {
return None;
}
Some(unsafe { &(*segment).slots[id % NODE_SEGMENT_SIZE] })
}
fn pop_free(&self) -> Option<NodeId> {
let mut head = self.free_head.load(Ordering::Acquire);
loop {
let encoded = (head & FREE_NODE_INDEX_MASK) as usize;
if encoded == FREE_NODE_NONE {
return None;
}
let id = encoded - 1;
let slot = self
.slot(id)
.expect("free node stack references an installed slot");
let next = slot.next_free.load(Ordering::Acquire);
let tag = (head >> FREE_NODE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << FREE_NODE_INDEX_BITS) | next as u64;
match self.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(id),
Err(actual) => head = actual,
}
}
}
fn push_free(&self, id: NodeId) {
let encoded = id.checked_add(1).expect("node index overflow");
assert!(
encoded <= FREE_NODE_INDEX_MASK as usize,
"node free index overflow"
);
let slot = self.slot(id).expect("retired node slot remains installed");
let mut head = self.free_head.load(Ordering::Acquire);
loop {
slot.next_free
.store((head & FREE_NODE_INDEX_MASK) as usize, Ordering::Release);
let tag = (head >> FREE_NODE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << FREE_NODE_INDEX_BITS) | encoded as u64;
match self.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return,
Err(actual) => head = actual,
}
}
}
fn push(&self, node: impl IntoTreeNode) -> NodeId {
let mut node = node.into_tree_node();
node.attach_payload_slabs(&self.payloads);
let node = self.node_slab.allocate(node);
let reused = self.pop_free();
let id = reused.unwrap_or_else(|| self.next.fetch_add(1, Ordering::AcqRel));
let segment_index = id / NODE_SEGMENT_SIZE;
assert!(
segment_index < MAX_NODE_SEGMENTS,
"B+ node arena exhausted its segmented metadata capacity"
);
let segment = self.segment(segment_index);
let slot_index = id % NODE_SEGMENT_SIZE;
let slot = unsafe { &(*segment).slots[slot_index] };
let record = Self::record_storage(segment, slot_index);
unsafe {
record.write(NodeRecord {
node,
retirement_scheduled: AtomicBool::new(false),
})
};
let published = slot.record.compare_exchange(
Shared::null(),
Shared::from(record as *const NodeRecord),
Ordering::Release,
Ordering::Acquire,
unsafe { unprotected() },
);
if published.is_err() {
unsafe { std::ptr::drop_in_place(record) };
panic!("B+ node slot published twice");
}
self.live.fetch_add(1, Ordering::Relaxed);
if reused.is_some() {
self.reused.fetch_add(1, Ordering::Relaxed);
}
id
}
fn get(&self, id: NodeId, guard: &Guard) -> NodeHandle {
self.try_get(id, guard)
.expect("B+ node slot was not published")
}
fn try_get(&self, id: NodeId, guard: &Guard) -> Option<NodeHandle> {
let record = self.slot(id)?.record.load(Ordering::Acquire, guard);
if record.is_null() {
return None;
}
Some(unsafe { record.deref() }.node.clone())
}
fn retire_later(self: &Arc<Self>, id: NodeId, guard: &Guard) -> bool {
let Some(slot) = self.slot(id) else {
return false;
};
let record = slot.record.load(Ordering::Acquire, guard);
if record.is_null() {
return false;
}
if unsafe { record.deref() }
.retirement_scheduled
.compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
.is_err()
{
return false;
}
let arena = Arc::clone(self);
guard.defer(move || arena.reclaim(id));
true
}
fn reclaim(&self, id: NodeId) {
let Some(slot) = self.slot(id) else { return };
let guard = unsafe { unprotected() };
let record = slot.record.swap(Shared::null(), Ordering::AcqRel, guard);
if record.is_null() {
return;
}
unsafe { std::ptr::drop_in_place(record.as_raw() as *mut NodeRecord) };
self.live.fetch_sub(1, Ordering::Relaxed);
self.retired.fetch_add(1, Ordering::Relaxed);
self.push_free(id);
}
fn len(&self) -> usize {
self.next.load(Ordering::Acquire)
}
#[cfg(test)]
fn allocated_segments(&self) -> usize {
self.segments
.iter()
.filter(|segment| {
let pointer = segment.load(Ordering::Acquire);
!pointer.is_null() && pointer != SEGMENT_INITIALIZING
})
.count()
}
fn allocated_metadata_blocks(&self) -> usize {
self.metadata_blocks
.iter()
.filter(|block| block.load(Ordering::Acquire) != 0)
.count()
+ self.node_slab.allocated_blocks()
+ self.payloads.allocated_blocks()
}
fn live(&self) -> usize {
self.live.load(Ordering::Relaxed)
}
fn retired(&self) -> u64 {
self.retired.load(Ordering::Relaxed)
}
fn reused(&self) -> u64 {
self.reused.load(Ordering::Relaxed)
}
}
impl Drop for NodeArena {
fn drop(&mut self) {
for segment in &self.segments {
let pointer = segment.load(Ordering::Relaxed);
if !pointer.is_null() && pointer != SEGMENT_INITIALIZING {
for slot in &unsafe { &*pointer }.slots {
let record = slot
.record
.swap(Shared::null(), Ordering::Relaxed, unsafe { unprotected() });
if !record.is_null() {
unsafe { std::ptr::drop_in_place(record.as_raw() as *mut NodeRecord) };
}
}
unsafe { std::ptr::drop_in_place(pointer) };
}
}
for block in &self.metadata_blocks {
let address = block.load(Ordering::Relaxed);
if address != 0 {
let _ = unsafe { release_metadata_block(address) };
}
}
}
}
pub(crate) struct AddressTree {
nodes: Arc<NodeArena>,
root: AtomicUsize,
collector: Collector,
span_slab: SpanSlabOwner,
epoch_id: usize,
root_replacements: AtomicU64,
root_collapse_operations: AtomicU64,
leaf_split_operations: AtomicU64,
parent_insert_operations: AtomicU64,
internal_split_operations: AtomicU64,
logical_remove_operations: AtomicU64,
leaf_upsert_operations: AtomicU64,
redirect_operations: AtomicU64,
left_redirect_operations: AtomicU64,
internal_redirect_operations: AtomicU64,
internal_redistribution_operations: AtomicU64,
parent_cleanup_operations: AtomicU64,
batch_replacement_operations: AtomicU64,
operation_help_calls: AtomicU64,
operation_aborts: AtomicU64,
candidate_discards: AtomicU64,
candidate_ticket: AtomicUsize,
}
#[derive(Clone, Copy, Debug, Default)]
pub(crate) struct TreeOperationStats {
pub root_replacements: u64,
pub root_collapses: u64,
pub leaf_splits: u64,
pub parent_inserts: u64,
pub internal_splits: u64,
pub logical_removes: u64,
pub leaf_upserts: u64,
pub redirects: u64,
pub cross_parent_redirects: u64,
pub internal_redirects: u64,
pub internal_redistributions: u64,
pub parent_cleanups: u64,
pub batch_replacements: u64,
pub help_calls: u64,
pub aborts: u64,
pub candidate_discards: u64,
pub node_slots: usize,
pub live_nodes: usize,
pub retired_nodes: u64,
pub reused_nodes: u64,
pub node_object_slots: usize,
pub live_node_objects: usize,
pub reused_node_objects: u64,
pub span_slots: usize,
pub live_spans: usize,
pub reused_spans: u64,
pub bitmap_slots: usize,
pub live_bitmaps: usize,
pub reused_bitmaps: u64,
pub payload_vector_slots: usize,
pub live_payload_vectors: usize,
pub reused_payload_vectors: u64,
pub metadata_blocks: usize,
pub metadata_reserved_bytes: usize,
}
impl AddressTree {
pub fn new() -> Self {
let root = TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
);
let nodes = Arc::new(NodeArena::new());
assert_eq!(nodes.push(root), 0);
Self {
nodes,
root: AtomicUsize::new(0),
collector: Collector::new(),
span_slab: SpanSlabOwner::new(),
epoch_id: NEXT_TREE_EPOCH_ID.fetch_add(1, Ordering::Relaxed),
root_replacements: AtomicU64::new(0),
root_collapse_operations: AtomicU64::new(0),
leaf_split_operations: AtomicU64::new(0),
parent_insert_operations: AtomicU64::new(0),
internal_split_operations: AtomicU64::new(0),
logical_remove_operations: AtomicU64::new(0),
leaf_upsert_operations: AtomicU64::new(0),
redirect_operations: AtomicU64::new(0),
left_redirect_operations: AtomicU64::new(0),
internal_redirect_operations: AtomicU64::new(0),
internal_redistribution_operations: AtomicU64::new(0),
parent_cleanup_operations: AtomicU64::new(0),
batch_replacement_operations: AtomicU64::new(0),
operation_help_calls: AtomicU64::new(0),
operation_aborts: AtomicU64::new(0),
candidate_discards: AtomicU64::new(0),
candidate_ticket: AtomicUsize::new(1),
}
}
pub fn operation_stats(&self) -> TreeOperationStats {
TreeOperationStats {
root_replacements: self.root_replacements.load(Ordering::Relaxed),
root_collapses: self.root_collapse_operations.load(Ordering::Relaxed),
leaf_splits: self.leaf_split_operations.load(Ordering::Relaxed),
parent_inserts: self.parent_insert_operations.load(Ordering::Relaxed),
internal_splits: self.internal_split_operations.load(Ordering::Relaxed),
logical_removes: self.logical_remove_operations.load(Ordering::Relaxed),
leaf_upserts: self.leaf_upsert_operations.load(Ordering::Relaxed),
redirects: self.redirect_operations.load(Ordering::Relaxed),
cross_parent_redirects: self.left_redirect_operations.load(Ordering::Relaxed),
internal_redirects: self.internal_redirect_operations.load(Ordering::Relaxed),
internal_redistributions: self
.internal_redistribution_operations
.load(Ordering::Relaxed),
parent_cleanups: self.parent_cleanup_operations.load(Ordering::Relaxed),
batch_replacements: self.batch_replacement_operations.load(Ordering::Relaxed),
help_calls: self.operation_help_calls.load(Ordering::Relaxed),
aborts: self.operation_aborts.load(Ordering::Relaxed),
candidate_discards: self.candidate_discards.load(Ordering::Relaxed),
node_slots: self.nodes.len(),
live_nodes: self.nodes.live(),
retired_nodes: self.nodes.retired(),
reused_nodes: self.nodes.reused(),
node_object_slots: self.nodes.node_slab.next.load(Ordering::Relaxed),
live_node_objects: self.nodes.node_slab.live.load(Ordering::Relaxed),
reused_node_objects: self.nodes.node_slab.reused.load(Ordering::Relaxed),
span_slots: self.span_slab.slots(),
live_spans: self.span_slab.live(),
reused_spans: self.span_slab.reused(),
bitmap_slots: self.span_slab.bitmap_slots(),
live_bitmaps: self.span_slab.live_bitmaps(),
reused_bitmaps: self.span_slab.reused_bitmaps(),
payload_vector_slots: self.nodes.payloads.slots(),
live_payload_vectors: self.nodes.payloads.live(),
reused_payload_vectors: self.nodes.payloads.reused(),
metadata_blocks: self.nodes.allocated_metadata_blocks()
+ self.span_slab.allocated_blocks(),
metadata_reserved_bytes: (self.nodes.allocated_metadata_blocks()
+ self.span_slab.allocated_blocks())
* METADATA_BLOCK_BYTES,
}
}
fn with_guard<R>(&self, use_guard: impl FnOnce(&Guard) -> R) -> R {
let handle = TREE_EPOCH_HANDLES.try_with(|handles| {
let mut handles = handles.borrow_mut();
if let Some((_, handle)) = handles.iter().find(|entry| entry.0 == self.epoch_id) {
return handle.as_ref() as *const LocalHandle;
}
handles.push((self.epoch_id, Box::new(self.collector.register())));
handles
.last()
.expect("tree epoch handle was inserted")
.1
.as_ref() as *const LocalHandle
});
match handle {
Ok(handle) => {
let guard = unsafe { &*handle }.pin();
use_guard(&guard)
}
Err(_) => {
let handle = self.collector.register();
let guard = handle.pin();
use_guard(&guard)
}
}
}
pub(crate) fn allocate_span(&self, descriptor: SpanDesc) -> SpanHandle {
self.span_slab.allocate(descriptor)
}
fn node(&self, id: NodeId) -> NodeHandle {
self.with_guard(|guard| self.nodes.get(id, guard))
}
fn node_guarded(&self, id: NodeId, guard: &Guard) -> NodeHandle {
self.nodes.get(id, guard)
}
fn append_node(&self, node: impl IntoTreeNode) -> NodeId {
self.nodes.push(node)
}
fn retire_node(&self, id: NodeId, guard: &Guard) -> bool {
self.nodes.retire_later(id, guard)
}
fn ensure_candidate<N: IntoTreeNode>(
&self,
slot: &AtomicUsize,
create: impl Fn() -> N,
guard: &Guard,
) -> NodeId {
loop {
let state = slot.load(Ordering::Acquire);
if state != NO_NODE && state & CANDIDATE_CREATING == 0 {
return state;
}
if state == NO_NODE {
let ticket = self.candidate_ticket.fetch_add(1, Ordering::Relaxed)
& (CANDIDATE_CREATING - 1);
let token = CANDIDATE_CREATING | ticket;
if slot
.compare_exchange(NO_NODE, token, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
let candidate = self.append_node(create());
match slot.compare_exchange(
token,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return candidate,
Err(_) => {
self.candidate_discards.fetch_add(1, Ordering::Relaxed);
self.retire_node(candidate, guard);
continue;
}
}
}
continue;
}
let mut observed = state;
for _ in 0..64 {
std::hint::spin_loop();
observed = slot.load(Ordering::Acquire);
if observed != state {
break;
}
}
if observed == state {
std::thread::yield_now();
let _ = slot.compare_exchange(state, NO_NODE, Ordering::AcqRel, Ordering::Acquire);
}
}
}
fn ensure_replacement_data(&self, descriptor: &OperationDescriptor, data: &NodeData) -> usize {
let installed = descriptor.replacement_data.load(Ordering::Acquire);
if installed != 0 {
return installed;
}
let origin = match &descriptor.kind {
OperationKind::RootReplace { .. } => "root replacement",
OperationKind::RootCollapse { .. } => "root collapse replacement",
OperationKind::LeafSplit { .. } => "leaf split replacement",
OperationKind::ParentInsert { .. } => "parent insert replacement",
OperationKind::InternalSplit { .. } => "internal split replacement",
OperationKind::LogicalRemove { .. } => "logical remove replacement",
OperationKind::LeafUpsert { .. } => "leaf upsert replacement",
OperationKind::Redirect { .. } => "redirect replacement",
OperationKind::LeftRedirect { .. } => "left redirect replacement",
OperationKind::RightRedirect { .. } => "right redirect replacement",
OperationKind::InternalRedistribute { .. } => "redistributed source replacement",
};
#[cfg(test)]
assert_payload_fence(data, descriptor.replacement_high, origin);
let candidate = Box::into_raw(Box::new(
NodePayload::new(descriptor.replacement_high, data.clone(), origin)
.freeze(&self.nodes.payloads),
)) as usize;
match descriptor.replacement_data.compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
unsafe { drop(Box::from_raw(candidate as *mut NodePayload)) };
installed
}
}
}
fn ensure_left_parent_replacement(&self, descriptor: &OperationDescriptor) -> usize {
let OperationKind::LeftRedirect {
parent_high,
parent_data,
parent_replacement_data,
..
} = &descriptor.kind
else {
unreachable!("parent replacement requested for a non-left redirect")
};
let installed = parent_replacement_data.load(Ordering::Acquire);
if installed != 0 {
return installed;
}
let candidate = Box::into_raw(Box::new(
NodePayload::new(
*parent_high,
parent_data.clone(),
"left redirect parent replacement",
)
.freeze(&self.nodes.payloads),
)) as usize;
match parent_replacement_data.compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
unsafe { drop(Box::from_raw(candidate as *mut NodePayload)) };
installed
}
}
}
fn ensure_left_payload_replacement(&self, descriptor: &OperationDescriptor) -> Option<usize> {
let OperationKind::LeftRedirect {
left_new_high,
left_data,
left_replacement_data,
..
} = &descriptor.kind
else {
unreachable!("left payload requested for a non-left redirect")
};
let data = left_data.as_ref()?;
let installed = left_replacement_data.load(Ordering::Acquire);
if installed != 0 {
return Some(installed);
}
let candidate = Box::into_raw(Box::new(
NodePayload::new(
*left_new_high,
data.clone(),
"internal left redirect replacement",
)
.freeze(&self.nodes.payloads),
)) as usize;
Some(
match left_replacement_data.compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
unsafe { drop(Box::from_raw(candidate as *mut NodePayload)) };
installed
}
},
)
}
fn ensure_right_parent_replacement(&self, descriptor: &OperationDescriptor) -> usize {
let OperationKind::RightRedirect {
parent_high,
parent_data,
parent_replacement_data,
..
} = &descriptor.kind
else {
unreachable!("right parent payload requested for another operation")
};
let installed = parent_replacement_data.load(Ordering::Acquire);
if installed != 0 {
return installed;
}
let candidate = Box::into_raw(Box::new(
NodePayload::new(
*parent_high,
parent_data.clone(),
"right redirect parent replacement",
)
.freeze(&self.nodes.payloads),
)) as usize;
match parent_replacement_data.compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
unsafe { drop(Box::from_raw(candidate as *mut NodePayload)) };
installed
}
}
}
fn ensure_right_payload_replacement(&self, descriptor: &OperationDescriptor) -> usize {
let OperationKind::RightRedirect {
right_high,
right_data,
right_replacement_data,
..
} = &descriptor.kind
else {
unreachable!("right sibling payload requested for another operation")
};
let installed = right_replacement_data.load(Ordering::Acquire);
if installed != 0 {
return installed;
}
let candidate = Box::into_raw(Box::new(
NodePayload::new(
*right_high,
right_data.clone(),
"internal right redirect replacement",
)
.freeze(&self.nodes.payloads),
)) as usize;
match right_replacement_data.compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
unsafe { drop(Box::from_raw(candidate as *mut NodePayload)) };
installed
}
}
}
fn ensure_redistribution_parent_replacement(&self, descriptor: &OperationDescriptor) -> usize {
let OperationKind::InternalRedistribute {
parent_high,
parent_data,
parent_replacement_data,
..
} = &descriptor.kind
else {
unreachable!("redistribution parent payload requested for another operation")
};
let installed = parent_replacement_data.load(Ordering::Acquire);
if installed != 0 {
return installed;
}
let candidate = Box::into_raw(Box::new(
NodePayload::new(
*parent_high,
parent_data.clone(),
"redistribution parent replacement",
)
.freeze(&self.nodes.payloads),
)) as usize;
match parent_replacement_data.compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
unsafe { drop(Box::from_raw(candidate as *mut NodePayload)) };
installed
}
}
}
fn ensure_redistribution_sibling_replacement(&self, descriptor: &OperationDescriptor) -> usize {
let OperationKind::InternalRedistribute {
new_sibling_high,
sibling_data,
sibling_replacement_data,
..
} = &descriptor.kind
else {
unreachable!("redistribution sibling payload requested for another operation")
};
let installed = sibling_replacement_data.load(Ordering::Acquire);
if installed != 0 {
return installed;
}
let candidate = Box::into_raw(Box::new(
NodePayload::new(
*new_sibling_high,
sibling_data.clone(),
"redistribution sibling replacement",
)
.freeze(&self.nodes.payloads),
)) as usize;
match sibling_replacement_data.compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
unsafe { drop(Box::from_raw(candidate as *mut NodePayload)) };
installed
}
}
}
fn attach_operation_slot(
&self,
node_id: NodeId,
operation: Shared<'_, OperationDescriptor>,
guard: &Guard,
) -> bool {
let node = self.node(node_id);
loop {
let phase = unsafe { operation.deref() }.phase.load(Ordering::Acquire);
match phase {
OP_LINKED | OP_PARENTED => return true,
OP_DONE | OP_ABORTED => return false,
OP_FROZEN => {}
OP_INIT => {
std::thread::yield_now();
continue;
}
_ => unreachable!("invalid operation phase while attaching a slot"),
}
match node.operation.compare_exchange(
Shared::null(),
operation,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => {
let phase = unsafe { operation.deref() }.phase.load(Ordering::Acquire);
if matches!(phase, OP_FROZEN | OP_LINKED | OP_PARENTED) {
return true;
}
let _ = node.operation.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
);
return false;
}
Err(error) if error.current == operation => return true,
Err(error) => {
if error.current.is_null() {
continue;
}
self.help_operation(node_id, &node, error.current, guard);
}
}
}
}
fn freeze_operation_slot(&self, node: &TreeNode, expected_version: u64) -> bool {
let frozen = VERSION_OPERATION_FROZEN | expected_version;
let mut observed = node.version.load(Ordering::Acquire);
if observed == expected_version.wrapping_add(1) {
for _ in 0..8 {
std::thread::yield_now();
observed = node.version.load(Ordering::Acquire);
if observed != expected_version.wrapping_add(1) {
break;
}
}
}
observed == frozen
|| (observed == expected_version
&& match node.version.compare_exchange(
expected_version,
frozen,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == frozen,
})
}
fn abort_left_redirect(&self, source: &TreeNode, descriptor: &OperationDescriptor) {
let OperationKind::LeftRedirect {
expected_version,
parent_id,
parent_expected_version,
left_id,
left_expected_version,
..
} = &descriptor.kind
else {
unreachable!("left redirect abort requested for another operation")
};
self.abort_frozen_payload(source, descriptor, *expected_version);
self.finish_frozen_version(&self.node(*parent_id), *parent_expected_version);
self.finish_frozen_version(&self.node(*left_id), *left_expected_version);
}
fn abort_right_redirect(&self, source: &TreeNode, descriptor: &OperationDescriptor) {
let OperationKind::RightRedirect {
expected_version,
parent_id,
parent_expected_version,
right_id,
right_expected_version,
..
} = &descriptor.kind
else {
unreachable!("right redirect abort requested for another operation")
};
self.abort_frozen_payload(source, descriptor, *expected_version);
self.finish_frozen_version(&self.node(*parent_id), *parent_expected_version);
self.finish_frozen_version(&self.node(*right_id), *right_expected_version);
}
fn abort_internal_redistribution(&self, source: &TreeNode, descriptor: &OperationDescriptor) {
let OperationKind::InternalRedistribute {
expected_version,
sibling_id,
sibling_expected_version,
parent_id,
parent_expected_version,
..
} = &descriptor.kind
else {
unreachable!("redistribution abort requested for another operation")
};
self.abort_frozen_payload(source, descriptor, *expected_version);
self.finish_frozen_version(&self.node(*sibling_id), *sibling_expected_version);
self.finish_frozen_version(&self.node(*parent_id), *parent_expected_version);
}
fn abort_frozen_payload(
&self,
node: &TreeNode,
descriptor: &OperationDescriptor,
expected_version: u64,
) {
let frozen = VERSION_OPERATION_FROZEN | expected_version;
let stable = expected_version.wrapping_add(2);
let _ = node
.version
.compare_exchange(frozen, stable, Ordering::Release, Ordering::Acquire);
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_ABORTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
fn finish_frozen_version(&self, node: &TreeNode, expected_version: u64) {
let frozen = VERSION_OPERATION_FROZEN | expected_version;
let stable = expected_version.wrapping_add(2);
let observed = node.version.load(Ordering::Acquire);
if observed == frozen {
let _ =
node.version
.compare_exchange(frozen, stable, Ordering::Release, Ordering::Acquire);
}
}
fn frozen_payload_matches(
&self,
node: &TreeNode,
descriptor: &OperationDescriptor,
expected_data: usize,
guard: &Guard,
) -> bool {
let current = node.data.load(Ordering::Acquire, guard).as_raw() as usize;
let replacement = descriptor.replacement_data.load(Ordering::Acquire);
current == expected_data || (replacement != 0 && current == replacement)
}
fn publish_multi_node_payload<'guard>(
&self,
descriptor: &OperationDescriptor,
bit: u8,
destination: &Atomic<NodePayload>,
expected_data: usize,
replacement: Shared<'guard, NodePayload>,
guard: &'guard Guard,
) -> bool {
if descriptor.payload_replaced.load(Ordering::Acquire) & bit != 0 {
return true;
}
if descriptor.phase.load(Ordering::Acquire) != OP_FROZEN {
return descriptor.payload_replaced.load(Ordering::Acquire) & bit != 0;
}
let expected = Shared::from(expected_data as *const NodePayload);
let published = match destination.compare_exchange(
expected,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => true,
Err(error) => error.current == replacement,
};
if published {
descriptor.payload_replaced.fetch_or(bit, Ordering::AcqRel);
true
} else {
descriptor.payload_replaced.load(Ordering::Acquire) & bit != 0
}
}
fn read_node<R>(
&self,
node_id: NodeId,
node: &TreeNode,
guard: &Guard,
read: impl Fn(usize, &NodeData) -> R,
) -> R {
loop {
self.help_node_operation(node_id, node, guard);
if let Some(result) = node.try_read_consistent(guard, &read) {
return result;
}
std::hint::spin_loop();
}
}
fn read_node_snapshot(
&self,
node_id: NodeId,
node: &TreeNode,
guard: &Guard,
) -> (u64, usize, usize, NodeData) {
loop {
self.help_node_operation(node_id, node, guard);
let version = node.version.load(Ordering::Acquire);
if version & (VERSION_OPERATION_FROZEN | 1) != 0 {
std::hint::spin_loop();
continue;
}
let shared = node.data.load(Ordering::Acquire, guard);
let payload = unsafe { shared.deref() };
let data = payload.data.clone();
if node.version.load(Ordering::Acquire) == version {
return (version, shared.as_raw() as usize, payload.high_key, data);
}
}
}
fn find_leaf(&self, key: usize, guard: &Guard) -> NodeId {
let mut node_id = self.root.load(Ordering::Acquire);
#[cfg(test)]
let mut hops = 0_usize;
loop {
#[cfg(test)]
{
hops += 1;
assert!(
hops < self.nodes.len().saturating_mul(4).saturating_add(1024),
"B+ lookup did not converge: key={key:#x} node={node_id}"
);
}
let node = self.node_guarded(node_id, guard);
let next = self.read_node(node_id, &node, guard, |high_key, data| {
let right = node.right_sibling.load(Ordering::Acquire);
if key >= high_key && right != NO_NODE {
return (Some(right), false);
}
match data {
NodeData::Leaf { .. } => (None, true),
NodeData::Internal { keys, children } => {
let child = keys.partition_point(|separator| key >= *separator);
let child = children[child];
self.node_guarded(child, guard)
.compare_parent(None, Some(node_id));
(Some(child), false)
}
NodeData::Redirect { target } => (Some(*target), false),
}
});
match next {
(Some(child), _) => node_id = child,
(None, true) => return node_id,
(None, false) => unreachable!(),
}
}
}
fn parent_contains(&self, parent_id: NodeId, child_id: NodeId, guard: &Guard) -> bool {
let parent = self.node_guarded(parent_id, guard);
self.read_node(parent_id, &parent, guard, |_, data| match data {
NodeData::Internal { children, .. } => children.contains(&child_id),
NodeData::Leaf { .. } | NodeData::Redirect { .. } => false,
})
}
fn find_actual_parent(&self, child_id: NodeId, guard: &Guard) -> Option<NodeId> {
let mut pending = vec![self.root.load(Ordering::Acquire)];
let mut seen = vec![false; self.nodes.len()];
while let Some(node_id) = pending.pop() {
if node_id >= seen.len() || seen[node_id] {
continue;
}
seen[node_id] = true;
let node = self.node_guarded(node_id, guard);
let Some((found, children)) = node.try_read_consistent(guard, |_, data| match data {
NodeData::Internal { children, .. } => {
(children.contains(&child_id), children.to_vec())
}
NodeData::Leaf { .. } | NodeData::Redirect { .. } => (false, Vec::new()),
}) else {
continue;
};
if found {
return Some(node_id);
}
pending.extend(children);
let right = node.right_sibling.load(Ordering::Acquire);
if right != NO_NODE {
pending.push(right);
}
}
None
}
fn find_actual_parent_for_key(
&self,
child_id: NodeId,
key: usize,
guard: &Guard,
) -> Option<NodeId> {
let mut pending = vec![self.root.load(Ordering::Acquire)];
let mut seen = vec![false; self.nodes.len()];
while let Some(node_id) = pending.pop() {
if node_id >= seen.len() || seen[node_id] {
continue;
}
seen[node_id] = true;
let node = self.node_guarded(node_id, guard);
let Some((matches, children)) =
node.try_read_consistent(guard, |high_key, data| match data {
NodeData::Internal { children, .. } => (
children.contains(&child_id)
&& (key < high_key
|| node.right_sibling.load(Ordering::Acquire) == NO_NODE),
children.to_vec(),
),
NodeData::Leaf { .. } | NodeData::Redirect { .. } => (false, Vec::new()),
})
else {
continue;
};
if matches {
return Some(node_id);
}
pending.extend(children);
let right = node.right_sibling.load(Ordering::Acquire);
if right != NO_NODE {
pending.push(right);
}
}
None
}
fn resolve_parent(&self, child_id: NodeId, child: &TreeNode, guard: &Guard) -> Option<NodeId> {
loop {
let hint = child.parent();
if let Some(parent_id) = hint {
if self.parent_contains(parent_id, child_id, guard) {
return Some(parent_id);
}
}
let actual = self.find_actual_parent(child_id, guard)?;
if child.compare_parent(hint, Some(actual)) || child.parent() == Some(actual) {
return Some(actual);
}
}
}
fn find_leaf_predecessor(&self, source_id: NodeId, guard: &Guard) -> Option<NodeId> {
let mut leaf_id = self.root.load(Ordering::Acquire);
loop {
let node = self.node_guarded(leaf_id, guard);
let next = self.read_node(leaf_id, &node, guard, |_, data| match data {
NodeData::Internal { children, .. } => Some(children[0]),
NodeData::Redirect { target } => Some(*target),
NodeData::Leaf { .. } => None,
});
let Some(next) = next else { break };
leaf_id = next;
}
loop {
let leaf = self.node_guarded(leaf_id, guard);
let right = self.read_node(leaf_id, &leaf, guard, |_, data| match data {
NodeData::Leaf { .. } => leaf.right_sibling.load(Ordering::Acquire),
NodeData::Redirect { target } => *target,
NodeData::Internal { .. } => NO_NODE,
});
if right == source_id {
return Some(leaf_id);
}
if right == NO_NODE || leaf_id == source_id {
return None;
}
leaf_id = right;
}
}
fn find_internal_predecessor(&self, source_id: NodeId, guard: &Guard) -> Option<NodeId> {
let mut pending = vec![self.root.load(Ordering::Acquire)];
let mut seen = vec![false; self.nodes.len()];
while let Some(node_id) = pending.pop() {
if node_id >= seen.len() {
seen.resize(self.nodes.len().max(node_id + 1), false);
}
if seen[node_id] {
continue;
}
seen[node_id] = true;
let node = self.node_guarded(node_id, guard);
let (is_internal, children, redirect) =
self.read_node(node_id, &node, guard, |_, data| match data {
NodeData::Internal { children, .. } => (true, children.to_vec(), None),
NodeData::Redirect { target } => (false, Vec::new(), Some(*target)),
NodeData::Leaf { .. } => (false, Vec::new(), None),
});
let right = node.right_sibling.load(Ordering::Acquire);
if is_internal && right == source_id {
return Some(node_id);
}
pending.extend(children);
if let Some(target) = redirect {
pending.push(target);
}
if right != NO_NODE {
pending.push(right);
}
}
None
}
fn splice_internal_predecessor(&self, source_id: NodeId, target_id: NodeId, guard: &Guard) {
loop {
let Some(predecessor_id) = self.find_internal_predecessor(source_id, guard) else {
return;
};
let predecessor = self.node_guarded(predecessor_id, guard);
match predecessor.right_sibling.compare_exchange(
source_id,
target_id,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => {}
Err(current) if current == target_id => {}
Err(_) => {
continue;
}
}
if self.find_internal_predecessor(source_id, guard).is_none() {
return;
}
}
}
pub fn insert(&self, key: usize, value: SpanHandle) {
self.with_guard(|guard| self.insert_guarded(key, value, guard));
}
pub fn replace_batch(&self, expected: &SpanHandle, replacements: &[SpanHandle]) -> bool {
debug_assert!(
replacements
.windows(2)
.all(|pair| pair[0].base < pair[1].base)
);
self.with_guard(|guard| self.replace_batch_guarded(expected, replacements, guard))
}
fn replace_batch_guarded(
&self,
expected: &SpanHandle,
replacements: &[SpanHandle],
guard: &Guard,
) -> bool {
#[cfg(test)]
let mut retries = 0_u32;
#[cfg(test)]
let mut fence_retries = 0_u32;
#[cfg(test)]
let mut candidate_fence_retries = 0_u32;
#[cfg(test)]
let mut publish_retries = 0_u32;
loop {
#[cfg(test)]
{
retries += 1;
assert!(
retries < 100_000,
"B+ batch replacement did not converge: key={:#x}, replacements={}, fence={fence_retries}, candidate_fence={candidate_fence_retries}, publish={publish_retries}",
expected.base,
replacements.len(),
);
}
let leaf_id = self.find_leaf(expected.base, guard);
let leaf = self.node(leaf_id);
let (version, expected_data, high_key, mut candidate) =
self.read_node_snapshot(leaf_id, &leaf, guard);
if expected.base >= high_key && leaf.right_sibling.load(Ordering::Acquire) != NO_NODE {
#[cfg(test)]
{
fence_retries += 1;
}
continue;
}
let NodeData::Leaf { entries } = &mut candidate else {
continue;
};
let Some(position) = entries
.binary_search_by_key(&expected.base, |entry| entry.0)
.ok()
else {
return false;
};
if !SpanHandle::ptr_eq(&entries[position].1, expected) {
return false;
}
entries.remove(position);
for replacement in replacements {
let Err(position) =
entries.binary_search_by_key(&replacement.base, |entry| entry.0)
else {
return false;
};
entries.insert(position, (replacement.base, replacement.clone()));
}
if leaf.right_sibling.load(Ordering::Acquire) != NO_NODE
&& entries.last().is_some_and(|entry| entry.0 >= high_key)
{
#[cfg(test)]
{
candidate_fence_retries += 1;
}
for replacement in replacements {
if let Ok(position) =
entries.binary_search_by_key(&replacement.base, |entry| entry.0)
{
entries.remove(position);
}
}
let mut published_here = 0;
if let Some(first) = replacements.first().filter(|entry| entry.base < high_key) {
let position = entries
.binary_search_by_key(&first.base, |entry| entry.0)
.expect_err("replacement key was removed from the source leaf");
entries.insert(position, (first.base, first.clone()));
published_here = 1;
}
if !leaf.compare_publish(
expected_data,
high_key,
candidate,
"cross-fence batch source replacement",
guard,
) {
#[cfg(test)]
{
publish_retries += 1;
}
continue;
}
for replacement in &replacements[published_here..] {
self.insert_guarded(replacement.base, replacement.clone(), guard);
}
self.batch_replacement_operations
.fetch_add(1, Ordering::Relaxed);
return true;
}
let published = if entries.len() <= FANOUT {
leaf.compare_publish(
expected_data,
high_key,
candidate,
"batch leaf replacement",
guard,
)
} else {
self.try_publish_leaf_split_candidate(
leaf_id,
version,
expected_data,
high_key,
candidate,
guard,
)
};
if published {
self.batch_replacement_operations
.fetch_add(1, Ordering::Relaxed);
return true;
}
#[cfg(test)]
{
publish_retries += 1;
}
}
}
fn insert_guarded(&self, key: usize, value: SpanHandle, guard: &Guard) {
#[cfg(test)]
let mut retries = 0_u32;
loop {
#[cfg(test)]
{
retries += 1;
}
let leaf_id = self.find_leaf(key, guard);
let leaf = self.node(leaf_id);
#[cfg(test)]
if retries >= 100_000 {
let operation = leaf.operation.load(Ordering::Acquire, guard);
let operation_phase = if operation.is_null() {
None
} else {
Some(unsafe { operation.deref() }.phase.load(Ordering::Acquire))
};
let bounds = leaf.try_read_consistent(guard, |_, data| match data {
NodeData::Leaf { entries } => (
entries.first().map(|entry| entry.0),
entries.last().map(|entry| entry.0),
entries.len(),
),
NodeData::Internal { .. } => (None, None, 0),
NodeData::Redirect { .. } => (None, None, 0),
});
panic!(
"B+ insert did not converge: key={key:#x} leaf={leaf_id} version={} \
high={:#x} right={} operation_phase={operation_phase:?} bounds={bounds:?}",
leaf.version.load(Ordering::Acquire),
leaf.high_key.load(Ordering::Acquire),
leaf.right_sibling.load(Ordering::Acquire),
);
}
let (version, expected_data, snapshot_high, mut snapshot) =
self.read_node_snapshot(leaf_id, &leaf, guard);
if key >= snapshot_high && leaf.right_sibling.load(Ordering::Acquire) != NO_NODE {
continue;
}
let NodeData::Leaf { entries } = &mut snapshot else {
continue;
};
let was_empty = entries.is_empty();
match entries.binary_search_by_key(&key, |entry| entry.0) {
Ok(index) => entries[index] = (key, value.clone()),
Err(_) if entries.len() >= FANOUT => {
if self.try_publish_leaf_split(
leaf_id,
version,
expected_data,
snapshot_high,
snapshot,
key,
value.clone(),
guard,
) {
return;
}
continue;
}
Err(index) => entries.insert(index, (key, value.clone())),
}
let publish_right = leaf.right_sibling.load(Ordering::Acquire);
if publish_right != NO_NODE
&& entries.last().is_some_and(|entry| entry.0 >= snapshot_high)
{
continue;
}
if was_empty {
if self.try_publish_leaf_upsert(
leaf_id,
version,
expected_data,
snapshot_high,
snapshot,
guard,
) {
return;
}
} else if leaf.compare_publish(
expected_data,
snapshot_high,
snapshot,
"lock-free leaf upsert",
guard,
) {
return;
}
}
}
#[allow(clippy::too_many_arguments)]
fn try_publish_leaf_split(
&self,
leaf_id: NodeId,
expected_version: u64,
expected_data: usize,
expected_high: usize,
mut data: NodeData,
key: usize,
value: SpanHandle,
guard: &Guard,
) -> bool {
let leaf = self.node_guarded(leaf_id, guard);
let old_right = leaf.right_sibling.load(Ordering::Acquire);
if key >= expected_high && old_right != NO_NODE {
return false;
}
let NodeData::Leaf { entries } = &mut data else {
return false;
};
let Err(position) = entries.binary_search_by_key(&key, |entry| entry.0) else {
return false;
};
entries.insert(position, (key, value));
self.try_publish_leaf_split_candidate(
leaf_id,
expected_version,
expected_data,
expected_high,
data,
guard,
)
}
fn try_publish_leaf_split_candidate(
&self,
leaf_id: NodeId,
expected_version: u64,
expected_data: usize,
expected_high: usize,
mut data: NodeData,
guard: &Guard,
) -> bool {
let leaf = self.node_guarded(leaf_id, guard);
let old_right = leaf.right_sibling.load(Ordering::Acquire);
let NodeData::Leaf { entries } = &mut data else {
return false;
};
if entries.len() <= FANOUT
|| (old_right != NO_NODE
&& entries.last().is_some_and(|entry| entry.0 >= expected_high))
{
return false;
}
let right_entries = entries.split_off(entries.len() / 2);
let separator = right_entries[0].0;
let old_high = expected_high;
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: separator,
kind: OperationKind::LeafSplit {
expected_version,
expected_data,
old_right,
old_high,
separator,
right_id: AtomicUsize::new(NO_NODE),
root_id: AtomicUsize::new(NO_NODE),
needs_root: self.root.load(Ordering::Acquire) == leaf_id,
left_data: data,
right_data: NodeData::Leaf {
entries: right_entries,
},
},
});
match leaf.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.leaf_split_operations.fetch_add(1, Ordering::Relaxed);
self.help_operation(leaf_id, &leaf, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(leaf_id, &leaf, error.current, guard);
}
false
}
}
}
#[allow(clippy::too_many_arguments)]
fn try_publish_parent_insert(
&self,
parent_id: NodeId,
expected_version: u64,
expected_data: usize,
expected_high: usize,
right_id: NodeId,
new_data: NodeData,
guard: &Guard,
) -> bool {
let parent = self.node(parent_id);
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind: OperationKind::ParentInsert {
expected_version,
expected_data,
right_id,
new_data,
},
});
match parent.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.parent_insert_operations
.fetch_add(1, Ordering::Relaxed);
self.help_operation(parent_id, &parent, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(parent_id, &parent, error.current, guard);
}
false
}
}
}
fn try_publish_internal_split(
&self,
node_id: NodeId,
expected_version: u64,
expected_data: usize,
expected_high: usize,
mut data: NodeData,
guard: &Guard,
) -> bool {
let node = self.node(node_id);
let NodeData::Internal { keys, children } = &mut data else {
return false;
};
let middle = keys.len() / 2;
let right_keys = keys.split_off(middle + 1);
let separator = keys
.pop()
.expect("overfull internal node has a middle separator");
let right_children = children.split_off(middle + 1);
let old_right = node.right_sibling.load(Ordering::Acquire);
let old_high = expected_high;
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: separator,
kind: OperationKind::InternalSplit {
expected_version,
expected_data,
old_right,
old_high,
separator,
right_id: AtomicUsize::new(NO_NODE),
root_id: AtomicUsize::new(NO_NODE),
needs_root: self.root.load(Ordering::Acquire) == node_id,
left_data: data,
right_data: NodeData::Internal {
keys: right_keys,
children: right_children.clone(),
},
moved_children: right_children.into_boxed_slice(),
},
});
match node.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.internal_split_operations
.fetch_add(1, Ordering::Relaxed);
self.help_operation(node_id, &node, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(node_id, &node, error.current, guard);
}
false
}
}
}
fn insert_into_parent_impl(
&self,
left_id: NodeId,
separator: usize,
right_id: NodeId,
skip_left_operation: bool,
) {
loop {
let left = self.node(left_id);
let handle = self.collector.register();
let guard = handle.pin();
if skip_left_operation && self.find_actual_parent(right_id, &guard).is_some() {
return;
}
if !skip_left_operation {
self.help_node_operation(left_id, &left, &guard);
}
let Some(parent_id) = self.resolve_parent(left_id, &left, &guard) else {
if self.root.load(Ordering::Acquire) != left_id {
std::thread::yield_now();
continue;
}
let root_id = self.append_node(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![separator].into(),
children: vec![left_id, right_id].into(),
},
));
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: 0,
kind: OperationKind::RootReplace {
left_id,
right_id,
root_id,
},
});
match left.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
&guard,
) {
Ok(operation) => {
self.root_replacements.fetch_add(1, Ordering::Relaxed);
self.help_operation(left_id, &left, operation, &guard);
let phase = unsafe { operation.deref() }.phase.load(Ordering::Acquire);
if phase == OP_DONE {
return;
}
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(left_id, &left, error.current, &guard);
}
}
}
continue;
};
let parent = self.node(parent_id);
self.help_node_operation(parent_id, &parent, &guard);
let (version, expected_data, expected_high, mut candidate) =
self.read_node_snapshot(parent_id, &parent, &guard);
if separator >= expected_high && parent.right_sibling.load(Ordering::Acquire) != NO_NODE
{
if let Some(actual) = self.find_actual_parent_for_key(left_id, separator, &guard) {
let hint = left.parent();
left.compare_parent(hint, Some(actual));
}
std::thread::yield_now();
continue;
}
if left.parent() != Some(parent_id) {
continue;
}
let NodeData::Internal { keys, children } = &mut candidate else {
continue;
};
let Some(position) = children.iter().position(|child| *child == left_id) else {
continue;
};
if children.get(position + 1) == Some(&right_id) {
self.node(right_id).compare_parent(None, Some(parent_id));
return;
}
if self.find_actual_parent(right_id, &guard).is_some() {
return;
}
let right = self.node(right_id);
match right.parent() {
None => {
if !right.compare_parent(None, Some(parent_id)) {
continue;
}
}
Some(existing) if existing == parent_id => {}
Some(_) => {
std::thread::yield_now();
continue;
}
}
keys.insert(position, separator);
children.insert(position + 1, right_id);
if children.len() <= FANOUT + 1 {
if self.try_publish_parent_insert(
parent_id,
version,
expected_data,
expected_high,
right_id,
candidate,
&guard,
) {
return;
}
if self.parent_contains(parent_id, right_id, &guard) {
return;
}
right.compare_parent(Some(parent_id), None);
continue;
}
if self.try_publish_internal_split(
parent_id,
version,
expected_data,
expected_high,
candidate,
&guard,
) {
return;
}
if self.parent_contains(parent_id, right_id, &guard) {
return;
}
right.compare_parent(Some(parent_id), None);
}
}
pub fn remove(&self, key: usize) -> Option<SpanHandle> {
self.with_guard(|guard| self.remove_guarded(key, guard))
}
fn remove_guarded(&self, key: usize, guard: &Guard) -> Option<SpanHandle> {
loop {
let leaf_id = self.find_leaf(key, guard);
let leaf = self.node(leaf_id);
let (version, expected_data, high_key, mut data) =
self.read_node_snapshot(leaf_id, &leaf, guard);
if key >= high_key && leaf.right_sibling.load(Ordering::Acquire) != NO_NODE {
continue;
}
let NodeData::Leaf { entries } = &mut data else {
continue;
};
let index = entries.binary_search_by_key(&key, |entry| entry.0).ok()?;
let result = entries.remove(index).1;
let became_empty = entries.is_empty();
if self.try_publish_logical_update(
leaf_id,
version,
expected_data,
high_key,
data,
&self.logical_remove_operations,
guard,
) {
if became_empty {
self.try_publish_redirect(leaf_id, guard);
}
return Some(result);
}
}
}
#[allow(clippy::too_many_arguments)]
fn try_publish_logical_update(
&self,
node_id: NodeId,
expected_version: u64,
expected_data: usize,
expected_high: usize,
new_data: NodeData,
operation_counter: &AtomicU64,
guard: &Guard,
) -> bool {
self.try_publish_payload_operation(
node_id,
expected_high,
OperationKind::LogicalRemove {
expected_version,
expected_data,
new_data,
},
operation_counter,
guard,
)
}
#[allow(clippy::too_many_arguments)]
fn try_publish_leaf_upsert(
&self,
node_id: NodeId,
expected_version: u64,
expected_data: usize,
expected_high: usize,
new_data: NodeData,
guard: &Guard,
) -> bool {
self.try_publish_payload_operation(
node_id,
expected_high,
OperationKind::LeafUpsert {
expected_version,
expected_data,
new_data,
},
&self.leaf_upsert_operations,
guard,
)
}
fn try_publish_payload_operation(
&self,
node_id: NodeId,
replacement_high: usize,
kind: OperationKind,
operation_counter: &AtomicU64,
guard: &Guard,
) -> bool {
let node = self.node(node_id);
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high,
kind,
});
match node.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
operation_counter.fetch_add(1, Ordering::Relaxed);
self.help_operation(node_id, &node, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(node_id, &node, error.current, guard);
}
false
}
}
}
fn try_publish_redirect(&self, leaf_id: NodeId, guard: &Guard) {
let leaf = self.node(leaf_id);
let (expected_version, expected_data, expected_high, data) =
self.read_node_snapshot(leaf_id, &leaf, guard);
if !matches!(&data, NodeData::Leaf { entries } if entries.is_empty()) {
return;
}
let right_id = leaf.right_sibling.load(Ordering::Acquire);
if right_id == NO_NODE || self.root.load(Ordering::Acquire) == leaf_id {
return;
}
let Some(kind) = self.redirect_operation_kind(
leaf_id,
expected_version,
expected_data,
expected_high,
right_id,
guard,
) else {
return;
};
let is_left_redirect = matches!(&kind, OperationKind::LeftRedirect { .. });
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind,
});
match leaf.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.redirect_operations.fetch_add(1, Ordering::Relaxed);
if is_left_redirect {
self.left_redirect_operations
.fetch_add(1, Ordering::Relaxed);
}
self.help_operation(leaf_id, &leaf, operation, guard);
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(leaf_id, &leaf, error.current, guard);
}
}
}
}
fn redirect_operation_kind(
&self,
source_id: NodeId,
expected_version: u64,
expected_data: usize,
expected_high: usize,
right_id: NodeId,
guard: &Guard,
) -> Option<OperationKind> {
let source = self.node(source_id);
let parent_id = self.resolve_parent(source_id, &source, guard)?;
let parent = self.node(parent_id);
let (parent_expected_version, parent_expected_data, parent_high, mut parent_data) =
self.read_node_snapshot(parent_id, &parent, guard);
let NodeData::Internal { keys, children } = &mut parent_data else {
return None;
};
let position = children.iter().position(|child| *child == source_id)?;
if position == 0 && children.len() == 1 {
if self.try_publish_internal_redirect(parent_id, guard) {
return self.redirect_operation_kind(
source_id,
expected_version,
expected_data,
expected_high,
right_id,
guard,
);
}
return None;
}
let (left_id, separator_position) = if let Some(left_position) = position.checked_sub(1) {
(children[left_position], left_position)
} else if let Some(predecessor) = self.find_leaf_predecessor(source_id, guard) {
(predecessor, 0)
} else if children.get(position + 1) == Some(&right_id) {
return Some(OperationKind::Redirect {
expected_version,
expected_data,
target: right_id,
});
} else {
return None;
};
let left = self.node(left_id);
let (left_expected_version, left_expected_data, left_old_high, left_data) =
self.read_node_snapshot(left_id, &left, guard);
if !matches!(left_data, NodeData::Leaf { .. })
|| left.right_sibling.load(Ordering::Acquire) != source_id
|| (position != 0 && keys.get(separator_position).copied() != Some(left_old_high))
{
return None;
}
children.remove(position);
keys.remove(separator_position);
Some(OperationKind::LeftRedirect {
source_id,
expected_version,
expected_data,
left_id,
left_expected_version,
left_expected_data,
left_old_high,
left_new_high: expected_high,
left_data: Some(left_data),
left_replacement_data: AtomicUsize::new(0),
moved_children: Box::new([]),
parent_id,
parent_expected_version,
parent_expected_data,
parent_high,
parent_data,
parent_replacement_data: AtomicUsize::new(0),
right_id,
})
}
fn try_publish_internal_redirect(&self, source_id: NodeId, guard: &Guard) -> bool {
self.try_publish_internal_left_redirect(source_id, guard)
|| self.try_publish_internal_right_redirect(source_id, guard)
|| self.try_publish_internal_redistribution(source_id, guard)
}
fn try_publish_internal_left_redirect(&self, source_id: NodeId, guard: &Guard) -> bool {
if self.root.load(Ordering::Acquire) == source_id {
return false;
}
let source = self.node(source_id);
let (expected_version, expected_data, source_high, source_data) =
self.read_node_snapshot(source_id, &source, guard);
let NodeData::Internal {
keys: source_keys,
children: source_children,
} = source_data
else {
return false;
};
if source_children.len() != 1 {
return false;
}
let Some(parent_id) = self.resolve_parent(source_id, &source, guard) else {
return false;
};
let parent = self.node(parent_id);
let (parent_expected_version, parent_expected_data, parent_high, mut parent_data) =
self.read_node_snapshot(parent_id, &parent, guard);
let NodeData::Internal { keys, children } = &mut parent_data else {
return false;
};
let Some(position) = children.iter().position(|child| *child == source_id) else {
return false;
};
let Some(left_position) = position.checked_sub(1) else {
return false;
};
let left_id = children[left_position];
let left = self.node(left_id);
let (left_expected_version, left_expected_data, left_old_high, left_data) =
self.read_node_snapshot(left_id, &left, guard);
let NodeData::Internal {
keys: mut left_keys,
children: mut left_children,
} = left_data
else {
return false;
};
if left.right_sibling.load(Ordering::Acquire) != source_id
|| keys.get(left_position).copied() != Some(left_old_high)
|| left_children.len() + source_children.len() > FANOUT + 1
{
return false;
}
left_keys.push(left_old_high);
left_keys.extend(source_keys);
left_children.extend(source_children.iter().copied());
children.remove(position);
keys.remove(left_position);
let right_id = source.right_sibling.load(Ordering::Acquire);
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: source_high,
kind: OperationKind::LeftRedirect {
source_id,
expected_version,
expected_data,
left_id,
left_expected_version,
left_expected_data,
left_old_high,
left_new_high: source_high,
left_data: Some(NodeData::Internal {
keys: left_keys,
children: left_children,
}),
left_replacement_data: AtomicUsize::new(0),
moved_children: source_children.into_boxed_slice(),
parent_id,
parent_expected_version,
parent_expected_data,
parent_high,
parent_data,
parent_replacement_data: AtomicUsize::new(0),
right_id,
},
});
match source.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.internal_redirect_operations
.fetch_add(1, Ordering::Relaxed);
self.redirect_operations.fetch_add(1, Ordering::Relaxed);
self.help_operation(source_id, &source, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(source_id, &source, error.current, guard);
}
false
}
}
}
fn try_publish_internal_right_redirect(&self, source_id: NodeId, guard: &Guard) -> bool {
if self.root.load(Ordering::Acquire) == source_id {
return false;
}
let source = self.node(source_id);
let (expected_version, expected_data, source_high, source_data) =
self.read_node_snapshot(source_id, &source, guard);
let NodeData::Internal {
keys: source_keys,
children: source_children,
} = source_data
else {
return false;
};
if source_children.len() != 1 {
return false;
}
let Some(parent_id) = self.resolve_parent(source_id, &source, guard) else {
return false;
};
let parent = self.node(parent_id);
let (parent_expected_version, parent_expected_data, parent_high, mut parent_data) =
self.read_node_snapshot(parent_id, &parent, guard);
let NodeData::Internal { keys, children } = &mut parent_data else {
return false;
};
let Some(position) = children.iter().position(|child| *child == source_id) else {
return false;
};
if position != 0 {
return false;
}
let Some(&right_id) = children.get(1) else {
return false;
};
if source.right_sibling.load(Ordering::Acquire) != right_id
|| keys.first().copied() != Some(source_high)
{
return false;
}
let right = self.node(right_id);
let (right_expected_version, right_expected_data, right_high, right_data) =
self.read_node_snapshot(right_id, &right, guard);
let NodeData::Internal {
keys: right_keys,
children: right_children,
} = right_data
else {
return false;
};
if source_children.len() + right_children.len() > FANOUT + 1 {
return false;
}
let mut merged_keys = source_keys;
merged_keys.push(source_high);
merged_keys.extend(right_keys);
let mut merged_children = source_children.clone();
merged_children.extend(right_children);
children.remove(0);
keys.remove(0);
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: source_high,
kind: OperationKind::RightRedirect {
source_id,
expected_version,
expected_data,
right_id,
right_expected_version,
right_expected_data,
right_high,
right_data: NodeData::Internal {
keys: merged_keys,
children: merged_children,
},
right_replacement_data: AtomicUsize::new(0),
moved_children: source_children.into_boxed_slice(),
parent_id,
parent_expected_version,
parent_expected_data,
parent_high,
parent_data,
parent_replacement_data: AtomicUsize::new(0),
},
});
match source.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.internal_redirect_operations
.fetch_add(1, Ordering::Relaxed);
self.redirect_operations.fetch_add(1, Ordering::Relaxed);
self.help_operation(source_id, &source, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(source_id, &source, error.current, guard);
}
false
}
}
}
fn try_publish_internal_redistribution(&self, source_id: NodeId, guard: &Guard) -> bool {
if self.root.load(Ordering::Acquire) == source_id {
return false;
}
let source = self.node(source_id);
let (expected_version, expected_data, old_source_high, source_data) =
self.read_node_snapshot(source_id, &source, guard);
let NodeData::Internal {
keys: source_keys,
children: source_children,
} = source_data
else {
return false;
};
if source_children.len() != 1 {
return false;
}
let Some(parent_id) = self.resolve_parent(source_id, &source, guard) else {
return false;
};
let parent = self.node(parent_id);
let (parent_expected_version, parent_expected_data, parent_high, mut parent_data) =
self.read_node_snapshot(parent_id, &parent, guard);
let NodeData::Internal { keys, children } = &mut parent_data else {
return false;
};
let Some(position) = children.iter().position(|child| *child == source_id) else {
return false;
};
let sibling_is_left = position > 0;
let sibling_id = if sibling_is_left {
children[position - 1]
} else if let Some(&right) = children.get(1) {
right
} else {
return false;
};
let separator_index = if sibling_is_left { position - 1 } else { 0 };
let sibling = self.node(sibling_id);
let (sibling_expected_version, sibling_expected_data, old_sibling_high, sibling_data) =
self.read_node_snapshot(sibling_id, &sibling, guard);
let NodeData::Internal {
keys: sibling_keys,
children: sibling_children,
} = sibling_data
else {
return false;
};
let total_children = source_children.len() + sibling_children.len();
if total_children <= FANOUT + 1 {
return false;
}
let (
new_source_high,
new_sibling_high,
new_source_data,
new_sibling_data,
moved_children,
separator,
) = if sibling_is_left {
if sibling.right_sibling.load(Ordering::Acquire) != source_id
|| keys.get(separator_index).copied() != Some(old_sibling_high)
{
return false;
}
let sibling_original_len = sibling_children.len();
let mut combined_keys = sibling_keys;
combined_keys.push(old_sibling_high);
combined_keys.extend(source_keys);
let mut combined_children = sibling_children;
combined_children.extend(source_children.iter().copied());
let sibling_count = total_children / 2;
let separator = combined_keys[sibling_count - 1];
let new_sibling_keys = combined_keys[..sibling_count - 1].to_vec();
let new_source_keys = combined_keys[sibling_count..].to_vec();
let new_sibling_children = combined_children[..sibling_count].to_vec();
let new_source_children = combined_children[sibling_count..].to_vec();
let moved_children = combined_children[sibling_count..sibling_original_len]
.to_vec()
.into_boxed_slice();
(
old_source_high,
separator,
NodeData::Internal {
keys: new_source_keys.into(),
children: new_source_children.into(),
},
NodeData::Internal {
keys: new_sibling_keys.into(),
children: new_sibling_children.into(),
},
moved_children,
separator,
)
} else {
if source.right_sibling.load(Ordering::Acquire) != sibling_id
|| keys.get(separator_index).copied() != Some(old_source_high)
{
return false;
}
let source_original_len = source_children.len();
let mut combined_keys = source_keys;
combined_keys.push(old_source_high);
combined_keys.extend(sibling_keys);
let mut combined_children = source_children;
combined_children.extend(sibling_children);
let source_count = total_children / 2;
let separator = combined_keys[source_count - 1];
let new_source_keys = combined_keys[..source_count - 1].to_vec();
let new_sibling_keys = combined_keys[source_count..].to_vec();
let new_source_children = combined_children[..source_count].to_vec();
let new_sibling_children = combined_children[source_count..].to_vec();
let moved_children = combined_children[source_original_len..source_count]
.to_vec()
.into_boxed_slice();
(
separator,
old_sibling_high,
NodeData::Internal {
keys: new_source_keys.into(),
children: new_source_children.into(),
},
NodeData::Internal {
keys: new_sibling_keys.into(),
children: new_sibling_children.into(),
},
moved_children,
separator,
)
};
keys[separator_index] = separator;
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: new_source_high,
kind: OperationKind::InternalRedistribute {
source_id,
expected_version,
expected_data,
old_source_high,
new_source_high,
source_data: new_source_data,
sibling_id,
sibling_expected_version,
sibling_expected_data,
old_sibling_high,
new_sibling_high,
sibling_data: new_sibling_data,
sibling_replacement_data: AtomicUsize::new(0),
moved_children,
parent_id,
parent_expected_version,
parent_expected_data,
parent_high,
parent_data,
parent_replacement_data: AtomicUsize::new(0),
},
});
match source.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.internal_redistribution_operations
.fetch_add(1, Ordering::Relaxed);
#[cfg(test)]
if PAUSE_REDISTRIBUTION_AFTER_PUBLISH.get() {
return false;
}
self.help_operation(source_id, &source, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(source_id, &source, error.current, guard);
}
false
}
}
}
pub fn get(&self, key: usize) -> Option<SpanHandle> {
self.with_guard(|guard| self.get_guarded(key, guard))
}
fn get_guarded(&self, key: usize, guard: &Guard) -> Option<SpanHandle> {
let leaf_id = self.find_leaf(key, guard);
let leaf = self.node(leaf_id);
self.read_node(leaf_id, &leaf, guard, |_, data| {
let NodeData::Leaf { entries } = data else {
return None;
};
entries
.binary_search_by_key(&key, |entry| entry.0)
.ok()
.map(|index| entries[index].1.clone())
})
}
#[allow(dead_code)]
pub fn containing(&self, address: usize) -> Option<SpanHandle> {
self.with_guard(|guard| self.containing_guarded(address, guard))
}
fn containing_guarded(&self, address: usize, guard: &Guard) -> Option<SpanHandle> {
let leaf_id = self.find_leaf(address, guard);
let leaf = self.node(leaf_id);
self.read_node(leaf_id, &leaf, guard, |_, data| {
let NodeData::Leaf { entries } = data else {
return None;
};
let position = entries.partition_point(|entry| entry.0 <= address);
let span = position
.checked_sub(1)
.and_then(|index| entries.get(index))?;
(address < span.1.base.checked_add(span.1.size)?).then(|| span.1.clone())
})
}
pub fn values(&self) -> Vec<SpanHandle> {
self.with_guard(|guard| self.values_guarded(guard))
}
fn values_guarded(&self, guard: &Guard) -> Vec<SpanHandle> {
let mut leaf = self.root.load(Ordering::Acquire);
loop {
let node = self.node_guarded(leaf, guard);
let next = self.read_node(leaf, &node, guard, |_, data| match data {
NodeData::Internal { children, .. } => Some(children[0]),
NodeData::Leaf { .. } => None,
NodeData::Redirect { target } => Some(*target),
});
match next {
Some(child) => leaf = child,
None => break,
}
}
let mut result = Vec::new();
loop {
let node = self.node_guarded(leaf, guard);
let (entries, next) = self.read_node(leaf, &node, guard, |_, data| match data {
NodeData::Leaf { entries } => (
entries
.iter()
.map(|entry| entry.1.clone())
.collect::<Vec<_>>(),
node.right_sibling.load(Ordering::Acquire),
),
NodeData::Redirect { target } => (Vec::new(), *target),
NodeData::Internal { .. } => (Vec::new(), NO_NODE),
});
result.extend(entries);
if next == NO_NODE {
break;
}
leaf = next;
}
result
}
pub fn validate(&self) -> Result<(), InvariantError> {
let handle = self.collector.register();
let guard = handle.pin();
let mut leaf_id = self.root.load(Ordering::Acquire);
loop {
let node = self.node_guarded(leaf_id, &guard);
let child = self.read_node(leaf_id, &node, &guard, |_, data| match data {
NodeData::Internal { children, .. } => Some(children[0]),
NodeData::Leaf { .. } => None,
NodeData::Redirect { target } => Some(*target),
});
let Some(child) = child else { break };
leaf_id = child;
}
let mut previous: Option<(NodeId, usize, usize, NodeId)> = None;
loop {
let node = self.node_guarded(leaf_id, &guard);
let right = node.right_sibling.load(Ordering::Acquire);
let (high_key, entries) = self.read_node(leaf_id, &node, &guard, |high_key, data| {
let entries = match data {
NodeData::Leaf { entries } => entries
.iter()
.map(|entry| entry.1.clone())
.collect::<Vec<_>>(),
NodeData::Internal { .. } | NodeData::Redirect { .. } => Vec::new(),
};
(high_key, entries)
});
for value in entries {
if let Some((previous_leaf, previous_base, previous_high, previous_right)) =
previous
{
if previous_base >= value.base {
return Err(InvariantError::new(format!(
"B+ tree leaf keys are not strictly ordered: leaf {previous_leaf} \
base {previous_base:#x} high {previous_high:#x} right \
{previous_right} -> leaf {leaf_id} base {:#x} high {high_key:#x} \
right {right}",
value.base
)));
}
}
if value.base.checked_add(value.size).is_none() {
return Err(InvariantError::new("span end address overflows"));
}
previous = Some((leaf_id, value.base, high_key, right));
}
if right == NO_NODE {
break;
}
leaf_id = right;
}
let mut pending = vec![self.root.load(Ordering::Acquire)];
let mut reachable = vec![false; self.nodes.len()];
let mut expected_parents = vec![None; self.nodes.len()];
while let Some(id) = pending.pop() {
if id >= reachable.len() || reachable[id] {
continue;
}
reachable[id] = true;
let node = self.node_guarded(id, &guard);
self.help_node_operation(id, &node, &guard);
if node.version.load(Ordering::Acquire) & 1 != 0 {
return Err(InvariantError::new("B+ node left write-locked"));
}
let (_, _, _, data) = self.read_node_snapshot(id, &node, &guard);
if let NodeData::Internal { keys, children } = data {
if keys.len() + 1 != children.len() {
return Err(InvariantError::new(
"internal node key/child count mismatch",
));
}
for child in children.iter().copied() {
if let Some(previous) = expected_parents[child] {
if previous != id {
return Err(InvariantError::new(format!(
"child {child} is indexed by both parents {previous} and {id}"
)));
}
} else {
expected_parents[child] = Some(id);
}
}
pending.extend(children);
}
let right = node.right_sibling.load(Ordering::Acquire);
if right != NO_NODE {
pending.push(right);
}
}
for (child, expected) in expected_parents.into_iter().enumerate() {
if let Some(expected) = expected {
let child_node = self.node_guarded(child, &guard);
let actual = child_node.parent();
if actual != Some(expected) {
child_node.compare_parent(actual, Some(expected));
let repaired = child_node.parent();
if repaired != Some(expected) {
return Err(InvariantError::new(format!(
"child {child} has parent hint {repaired:?}, expected {expected}"
)));
}
}
}
}
Ok(())
}
pub fn metadata_bytes(&self) -> usize {
let handle = self.collector.register();
let guard = handle.pin();
let operations = self.operation_stats();
let mut total = size_of::<AddressTree>()
+ size_of::<NodeArena>()
+ size_of::<TreeNodeSlab>()
+ self.nodes.payloads.control_bytes()
+ self.span_slab.control_bytes()
+ operations.metadata_reserved_bytes;
let mut pending = vec![self.root.load(Ordering::Acquire)];
let mut seen = vec![false; self.nodes.len()];
while let Some(id) = pending.pop() {
if id >= seen.len() || seen[id] {
continue;
}
seen[id] = true;
let node = self.node_guarded(id, &guard);
self.help_node_operation(id, &node, &guard);
let data = node.data_clone(&guard);
total += size_of::<NodePayload>();
match data {
NodeData::Leaf { entries } => {
debug_assert_eq!(entries.capacity(), entries.len());
}
NodeData::Internal { keys, children } => {
debug_assert_eq!(keys.capacity(), keys.len());
debug_assert_eq!(children.capacity(), children.len());
pending.extend(children);
}
NodeData::Redirect { target } => pending.push(target),
}
let right = node.right_sibling.load(Ordering::Acquire);
if right != NO_NODE {
pending.push(right);
}
}
total
}
fn help_node_operation(&self, node_id: NodeId, node: &TreeNode, guard: &Guard) {
let operation = node.operation.load(Ordering::Acquire, guard);
if !operation.is_null() {
self.help_operation(node_id, node, operation, guard);
}
}
fn finish_split_parent(
&self,
node_id: NodeId,
separator: usize,
right_id: &AtomicUsize,
root_id: &AtomicUsize,
needs_root: bool,
guard: &Guard,
) -> bool {
let node = self.node(node_id);
let right_id = right_id.load(Ordering::Acquire);
debug_assert_ne!(right_id, NO_NODE);
if self.find_actual_parent(right_id, guard).is_some() {
return true;
}
if node.parent().is_some() {
self.insert_into_parent_impl(node_id, separator, right_id, true);
return true;
}
if !needs_root || self.root.load(Ordering::Acquire) != node_id {
std::thread::yield_now();
return false;
}
let installed_root = self.ensure_candidate(
root_id,
|| {
TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![separator].into(),
children: vec![node_id, right_id].into(),
},
)
},
guard,
);
let current = self.root.load(Ordering::Acquire);
let linked = current == installed_root
|| (current == node_id
&& match self.root.compare_exchange(
node_id,
installed_root,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == installed_root,
});
if linked {
node.compare_parent(None, Some(installed_root));
self.node(right_id)
.compare_parent(None, Some(installed_root));
}
linked
}
fn prepare_redirect_parent(&self, node_id: NodeId, target: NodeId, guard: &Guard) -> bool {
loop {
let redirect = self.node(node_id);
let Some(parent_id) = self.resolve_parent(node_id, &redirect, guard) else {
return self.find_actual_parent(node_id, guard).is_none();
};
let parent = self.node(parent_id);
let (version, expected_data, high_key, mut candidate) =
self.read_node_snapshot(parent_id, &parent, guard);
let NodeData::Internal { keys, children } = &mut candidate else {
continue;
};
let Some(position) = children.iter().position(|child| *child == node_id) else {
return true;
};
if children.get(position + 1) != Some(&target) {
return false;
}
children.remove(position);
keys.remove(position);
if self.try_publish_logical_update(
parent_id,
version,
expected_data,
high_key,
candidate,
&self.parent_cleanup_operations,
guard,
) || !self.parent_contains(parent_id, node_id, guard)
{
if !self.try_collapse_root(parent_id, guard) {
self.try_publish_internal_redirect(parent_id, guard);
}
return true;
}
}
}
fn try_collapse_root(&self, root_id: NodeId, guard: &Guard) -> bool {
if self.root.load(Ordering::Acquire) != root_id {
return false;
}
let root = self.node(root_id);
let (expected_version, expected_data, expected_high, data) =
self.read_node_snapshot(root_id, &root, guard);
let child_id = match data {
NodeData::Internal { children, .. } if children.len() == 1 => children[0],
_ => return false,
};
let descriptor = Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind: OperationKind::RootCollapse {
expected_version,
expected_data,
child_id,
},
});
match root.operation.compare_exchange(
Shared::null(),
descriptor,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(operation) => {
self.root_collapse_operations
.fetch_add(1, Ordering::Relaxed);
self.help_operation(root_id, &root, operation, guard);
unsafe { operation.deref() }.phase.load(Ordering::Acquire) == OP_DONE
}
Err(error) => {
if !error.current.is_null() {
self.help_operation(root_id, &root, error.current, guard);
}
self.root.load(Ordering::Acquire) == child_id
}
}
}
fn help_operation(
&self,
node_id: NodeId,
node: &TreeNode,
operation: Shared<'_, OperationDescriptor>,
guard: &Guard,
) {
self.operation_help_calls.fetch_add(1, Ordering::Relaxed);
let descriptor = unsafe { operation.deref() };
let redirect_source = match &descriptor.kind {
OperationKind::LeftRedirect { source_id, .. }
| OperationKind::RightRedirect { source_id, .. }
| OperationKind::InternalRedistribute { source_id, .. } => Some(*source_id),
_ => None,
};
if let Some(source_id) = redirect_source {
if node_id != source_id {
let source = self.node(source_id);
self.help_operation(source_id, &source, operation, guard);
return;
}
}
#[cfg(test)]
let mut stalled_iterations = 0_u32;
loop {
#[cfg(test)]
{
stalled_iterations = stalled_iterations.wrapping_add(1);
assert!(
stalled_iterations < 1_000_000,
"stalled tree helper: node={node_id} kind={} phase={} version={}",
match &descriptor.kind {
OperationKind::RootReplace { .. } => "root-replace",
OperationKind::RootCollapse { .. } => "root-collapse",
OperationKind::LeafSplit { .. } => "leaf-split",
OperationKind::ParentInsert { .. } => "parent-insert",
OperationKind::InternalSplit { .. } => "internal-split",
OperationKind::LogicalRemove { .. } => "logical-remove",
OperationKind::LeafUpsert { .. } => "leaf-upsert",
OperationKind::Redirect { .. } => "redirect",
OperationKind::LeftRedirect { .. } => "left-redirect",
OperationKind::RightRedirect { .. } => "right-redirect",
OperationKind::InternalRedistribute { .. } => "internal-redistribute",
},
descriptor.phase.load(Ordering::Acquire),
node.version.load(Ordering::Acquire),
);
}
match descriptor.phase.load(Ordering::Acquire) {
OP_INIT => match &descriptor.kind {
OperationKind::RootReplace { .. } => {
let _ = descriptor.phase.compare_exchange(
OP_INIT,
OP_FROZEN,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::RootCollapse {
expected_version, ..
}
| OperationKind::LeafSplit {
expected_version, ..
}
| OperationKind::ParentInsert {
expected_version, ..
}
| OperationKind::InternalSplit {
expected_version, ..
}
| OperationKind::LogicalRemove {
expected_version, ..
}
| OperationKind::LeafUpsert {
expected_version, ..
}
| OperationKind::Redirect {
expected_version, ..
}
| OperationKind::LeftRedirect {
expected_version, ..
}
| OperationKind::RightRedirect {
expected_version, ..
}
| OperationKind::InternalRedistribute {
expected_version, ..
} => {
let frozen = VERSION_OPERATION_FROZEN | *expected_version;
let mut observed = node.version.load(Ordering::Acquire);
if observed == expected_version.wrapping_add(1) {
for _ in 0..8 {
std::thread::yield_now();
observed = node.version.load(Ordering::Acquire);
if observed != expected_version.wrapping_add(1) {
break;
}
}
}
let acquired = observed == frozen
|| (observed == *expected_version
&& match node.version.compare_exchange(
*expected_version,
frozen,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == frozen,
});
let next = if acquired { OP_FROZEN } else { OP_ABORTED };
let _ = descriptor.phase.compare_exchange(
OP_INIT,
next,
Ordering::AcqRel,
Ordering::Acquire,
);
}
},
OP_FROZEN => match &descriptor.kind {
OperationKind::RootReplace {
left_id, root_id, ..
} => {
let current = self.root.load(Ordering::Acquire);
let linked = current == *root_id
|| (current == *left_id
&& match self.root.compare_exchange(
*left_id,
*root_id,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == *root_id,
});
if linked {
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
} else {
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_ABORTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
OperationKind::RootCollapse {
expected_version,
expected_data,
child_id,
} => {
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard) {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
let expected = Shared::from(*expected_data as *const NodePayload);
let redirect_data = NodeData::Redirect { target: *child_id };
let replacement =
Shared::from(self.ensure_replacement_data(descriptor, &redirect_data)
as *const NodePayload);
let replaced = match node.data.compare_exchange(
expected,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => true,
Err(error) => error.current == replacement,
};
if !replaced {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
descriptor.payload_replaced.store(1, Ordering::Release);
let current = self.root.load(Ordering::Acquire);
let linked = current == *child_id
|| (current == node_id
&& match self.root.compare_exchange(
node_id,
*child_id,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == *child_id,
});
if linked {
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
} else {
self.abort_frozen_payload(node, descriptor, *expected_version);
}
}
OperationKind::LeafSplit {
expected_version,
expected_data,
old_right,
old_high,
right_id,
left_data,
right_data,
..
} => {
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard) {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
#[cfg(test)]
{
let current = node.data.load(Ordering::Acquire, guard);
let current = unsafe { current.deref() };
let current_last = match ¤t.data {
NodeData::Leaf { entries } => entries.last().map(|entry| entry.0),
NodeData::Internal { keys, .. } => keys.last().copied(),
NodeData::Redirect { .. } => None,
};
assert_payload_fence(
right_data,
*old_high,
&format!(
"leaf split {node_id} right candidate; source id={} origin={} \
created_high={:#x} created_last={:#x?} current_last={:#x?}",
current.debug_id,
current.debug_origin,
current.debug_created_high,
current.debug_created_last,
current_last,
),
);
}
let published_right = self.ensure_candidate(
right_id,
|| {
TreeNode::new(
None,
(*old_right != NO_NODE).then_some(*old_right),
*old_high,
right_data.clone(),
)
},
guard,
);
let expected = Shared::from(*expected_data as *const NodePayload);
let replacement =
Shared::from(self.ensure_replacement_data(descriptor, left_data)
as *const NodePayload);
let replaced = match node.data.compare_exchange(
expected,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => true,
Err(error) => error.current == replacement,
};
if !replaced {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
descriptor.payload_replaced.store(1, Ordering::Release);
let linked = match node.right_sibling.compare_exchange(
*old_right,
published_right,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == published_right,
};
if replaced && linked {
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
OperationKind::ParentInsert {
expected_version,
expected_data,
new_data,
..
} => {
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard) {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
let expected = Shared::from(*expected_data as *const NodePayload);
let replacement =
Shared::from(self.ensure_replacement_data(descriptor, new_data)
as *const NodePayload);
let replaced = match node.data.compare_exchange(
expected,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => true,
Err(error) => error.current == replacement,
};
if !replaced {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
if let NodeData::Internal { children, .. } = new_data {
for child in children.iter().copied() {
self.node(child).compare_parent(None, Some(node_id));
}
}
descriptor.payload_replaced.store(1, Ordering::Release);
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::InternalSplit {
expected_version,
expected_data,
old_right,
old_high,
right_id,
left_data,
right_data,
moved_children,
..
} => {
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard) {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
#[cfg(test)]
assert_payload_fence(
right_data,
*old_high,
&format!("internal split {node_id} right candidate"),
);
let published_right = self.ensure_candidate(
right_id,
|| {
TreeNode::new(
None,
(*old_right != NO_NODE).then_some(*old_right),
*old_high,
right_data.clone(),
)
},
guard,
);
let expected = Shared::from(*expected_data as *const NodePayload);
let replacement =
Shared::from(self.ensure_replacement_data(descriptor, left_data)
as *const NodePayload);
let replaced = match node.data.compare_exchange(
expected,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => true,
Err(error) => error.current == replacement,
};
if !replaced {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
for child in moved_children.iter().copied() {
let child = self.node(child);
if !child.compare_parent(Some(node_id), Some(published_right)) {
child.compare_parent(None, Some(published_right));
}
}
descriptor.payload_replaced.store(1, Ordering::Release);
let linked = match node.right_sibling.compare_exchange(
*old_right,
published_right,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == published_right,
};
if replaced && linked {
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
OperationKind::LogicalRemove {
expected_version,
expected_data,
new_data,
}
| OperationKind::LeafUpsert {
expected_version,
expected_data,
new_data,
} => {
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard) {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
let expected = Shared::from(*expected_data as *const NodePayload);
let replacement =
Shared::from(self.ensure_replacement_data(descriptor, new_data)
as *const NodePayload);
let replaced = match node.data.compare_exchange(
expected,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => true,
Err(error) => error.current == replacement,
};
if !replaced {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
descriptor.payload_replaced.store(1, Ordering::Release);
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::Redirect {
expected_version,
expected_data,
target,
} => {
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard) {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
if !self.prepare_redirect_parent(node_id, *target, guard) {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
let expected = Shared::from(*expected_data as *const NodePayload);
let redirect_data = NodeData::Redirect { target: *target };
let replacement =
Shared::from(self.ensure_replacement_data(descriptor, &redirect_data)
as *const NodePayload);
let replaced = match node.data.compare_exchange(
expected,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => true,
Err(error) => error.current == replacement,
};
if !replaced {
self.abort_frozen_payload(node, descriptor, *expected_version);
continue;
}
descriptor.payload_replaced.store(1, Ordering::Release);
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::LeftRedirect {
expected_data,
left_id,
left_expected_version,
left_expected_data,
left_old_high,
left_new_high,
left_replacement_data,
parent_id,
parent_expected_version,
parent_expected_data,
parent_replacement_data,
right_id,
..
} => {
let parent = self.node(*parent_id);
let left = self.node(*left_id);
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard)
|| !self.attach_operation_slot(*parent_id, operation, guard)
|| !self.attach_operation_slot(*left_id, operation, guard)
|| !self.freeze_operation_slot(&parent, *parent_expected_version)
|| !self.freeze_operation_slot(&left, *left_expected_version)
{
self.abort_left_redirect(node, descriptor);
continue;
}
if descriptor.phase.load(Ordering::Acquire) != OP_FROZEN {
self.finish_frozen_version(&parent, *parent_expected_version);
self.finish_frozen_version(&left, *left_expected_version);
continue;
}
let source_current =
node.data.load(Ordering::Acquire, guard).as_raw() as usize;
let source_installed = descriptor.replacement_data.load(Ordering::Acquire);
let parent_current =
parent.data.load(Ordering::Acquire, guard).as_raw() as usize;
let parent_installed = parent_replacement_data.load(Ordering::Acquire);
let left_current =
left.data.load(Ordering::Acquire, guard).as_raw() as usize;
let left_installed = left_replacement_data.load(Ordering::Acquire);
let right_current = left.right_sibling.load(Ordering::Acquire);
let high_current = left.high_key.load(Ordering::Acquire);
let valid = (source_current == *expected_data
|| (source_installed != 0 && source_current == source_installed))
&& (parent_current == *parent_expected_data
|| (parent_installed != 0 && parent_current == parent_installed))
&& (left_current == *left_expected_data
|| (left_installed != 0 && left_current == left_installed))
&& (right_current == node_id || right_current == *right_id)
&& (high_current == *left_old_high || high_current == *left_new_high);
if !valid {
self.abort_left_redirect(node, descriptor);
continue;
}
let source_data = NodeData::Redirect { target: *left_id };
let source_replacement =
Shared::from(self.ensure_replacement_data(descriptor, &source_data)
as *const NodePayload);
let parent_replacement =
Shared::from(self.ensure_left_parent_replacement(descriptor)
as *const NodePayload);
let left_replacement = Shared::from(
self.ensure_left_payload_replacement(descriptor)
.expect("left redirect must replace the left payload")
as *const NodePayload,
);
if descriptor.phase.load(Ordering::Acquire) != OP_FROZEN {
self.finish_frozen_version(&parent, *parent_expected_version);
self.finish_frozen_version(&left, *left_expected_version);
continue;
}
if descriptor.payload_replaced.load(Ordering::Acquire) & 4 == 0 {
let right_linked = left
.right_sibling
.compare_exchange(
node_id,
*right_id,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
|| left.right_sibling.load(Ordering::Acquire) == *right_id;
let high_linked = left
.high_key
.compare_exchange(
*left_old_high,
*left_new_high,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
|| left.high_key.load(Ordering::Acquire) == *left_new_high;
assert!(
(right_linked && high_linked)
|| descriptor.payload_replaced.load(Ordering::Acquire) & 4 != 0,
"left redirect link mismatch"
);
}
assert!(self.publish_multi_node_payload(
descriptor,
4,
&left.data,
*left_expected_data,
left_replacement,
guard,
));
assert!(self.publish_multi_node_payload(
descriptor,
2,
&parent.data,
*parent_expected_data,
parent_replacement,
guard,
));
assert!(self.publish_multi_node_payload(
descriptor,
1,
&node.data,
*expected_data,
source_replacement,
guard,
));
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::RightRedirect {
expected_data,
right_id,
right_expected_version,
right_expected_data,
right_replacement_data,
parent_id,
parent_expected_version,
parent_expected_data,
parent_replacement_data,
..
} => {
let parent = self.node(*parent_id);
let right = self.node(*right_id);
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard)
|| !self.attach_operation_slot(*parent_id, operation, guard)
|| !self.attach_operation_slot(*right_id, operation, guard)
|| !self.freeze_operation_slot(&parent, *parent_expected_version)
|| !self.freeze_operation_slot(&right, *right_expected_version)
{
self.abort_right_redirect(node, descriptor);
continue;
}
if descriptor.phase.load(Ordering::Acquire) != OP_FROZEN {
self.finish_frozen_version(&parent, *parent_expected_version);
self.finish_frozen_version(&right, *right_expected_version);
continue;
}
let source_current =
node.data.load(Ordering::Acquire, guard).as_raw() as usize;
let source_installed = descriptor.replacement_data.load(Ordering::Acquire);
let parent_current =
parent.data.load(Ordering::Acquire, guard).as_raw() as usize;
let parent_installed = parent_replacement_data.load(Ordering::Acquire);
let right_current =
right.data.load(Ordering::Acquire, guard).as_raw() as usize;
let right_installed = right_replacement_data.load(Ordering::Acquire);
let valid = (source_current == *expected_data
|| (source_installed != 0 && source_current == source_installed))
&& (parent_current == *parent_expected_data
|| (parent_installed != 0 && parent_current == parent_installed))
&& (right_current == *right_expected_data
|| (right_installed != 0 && right_current == right_installed));
if !valid {
self.abort_right_redirect(node, descriptor);
continue;
}
let source_data = NodeData::Redirect { target: *right_id };
let source_replacement =
Shared::from(self.ensure_replacement_data(descriptor, &source_data)
as *const NodePayload);
let parent_replacement =
Shared::from(self.ensure_right_parent_replacement(descriptor)
as *const NodePayload);
let right_replacement =
Shared::from(self.ensure_right_payload_replacement(descriptor)
as *const NodePayload);
if descriptor.phase.load(Ordering::Acquire) != OP_FROZEN {
self.finish_frozen_version(&parent, *parent_expected_version);
self.finish_frozen_version(&right, *right_expected_version);
continue;
}
assert!(self.publish_multi_node_payload(
descriptor,
4,
&right.data,
*right_expected_data,
right_replacement,
guard,
));
assert!(self.publish_multi_node_payload(
descriptor,
2,
&parent.data,
*parent_expected_data,
parent_replacement,
guard,
));
assert!(self.publish_multi_node_payload(
descriptor,
1,
&node.data,
*expected_data,
source_replacement,
guard,
));
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::InternalRedistribute {
expected_data,
old_source_high,
new_source_high,
source_data,
sibling_id,
sibling_expected_version,
sibling_expected_data,
old_sibling_high,
new_sibling_high,
sibling_replacement_data,
parent_id,
parent_expected_version,
parent_expected_data,
parent_replacement_data,
..
} => {
let parent = self.node(*parent_id);
let sibling = self.node(*sibling_id);
if !self.frozen_payload_matches(node, descriptor, *expected_data, guard)
|| !self.attach_operation_slot(*parent_id, operation, guard)
|| !self.attach_operation_slot(*sibling_id, operation, guard)
|| !self.freeze_operation_slot(&parent, *parent_expected_version)
|| !self.freeze_operation_slot(&sibling, *sibling_expected_version)
{
self.abort_internal_redistribution(node, descriptor);
continue;
}
if descriptor.phase.load(Ordering::Acquire) != OP_FROZEN {
self.finish_frozen_version(&parent, *parent_expected_version);
self.finish_frozen_version(&sibling, *sibling_expected_version);
continue;
}
let source_current =
node.data.load(Ordering::Acquire, guard).as_raw() as usize;
let source_installed = descriptor.replacement_data.load(Ordering::Acquire);
let parent_current =
parent.data.load(Ordering::Acquire, guard).as_raw() as usize;
let parent_installed = parent_replacement_data.load(Ordering::Acquire);
let sibling_current =
sibling.data.load(Ordering::Acquire, guard).as_raw() as usize;
let sibling_installed = sibling_replacement_data.load(Ordering::Acquire);
let source_high = node.high_key.load(Ordering::Acquire);
let sibling_high = sibling.high_key.load(Ordering::Acquire);
let valid = (source_current == *expected_data
|| (source_installed != 0 && source_current == source_installed))
&& (parent_current == *parent_expected_data
|| (parent_installed != 0 && parent_current == parent_installed))
&& (sibling_current == *sibling_expected_data
|| (sibling_installed != 0
&& sibling_current == sibling_installed))
&& (source_high == *old_source_high || source_high == *new_source_high)
&& (sibling_high == *old_sibling_high
|| sibling_high == *new_sibling_high);
if !valid {
self.abort_internal_redistribution(node, descriptor);
continue;
}
let source_replacement =
Shared::from(self.ensure_replacement_data(descriptor, source_data)
as *const NodePayload);
let parent_replacement =
Shared::from(self.ensure_redistribution_parent_replacement(descriptor)
as *const NodePayload);
let sibling_replacement = Shared::from(
self.ensure_redistribution_sibling_replacement(descriptor)
as *const NodePayload,
);
if descriptor.phase.load(Ordering::Acquire) != OP_FROZEN {
self.finish_frozen_version(&parent, *parent_expected_version);
self.finish_frozen_version(&sibling, *sibling_expected_version);
continue;
}
if descriptor.payload_replaced.load(Ordering::Acquire) == 0 {
let source_high_replaced = node
.high_key
.compare_exchange(
*old_source_high,
*new_source_high,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
|| node.high_key.load(Ordering::Acquire) == *new_source_high;
let sibling_high_replaced = sibling
.high_key
.compare_exchange(
*old_sibling_high,
*new_sibling_high,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
|| sibling.high_key.load(Ordering::Acquire) == *new_sibling_high;
assert!(
(source_high_replaced && sibling_high_replaced)
|| descriptor.payload_replaced.load(Ordering::Acquire) != 0,
"redistribution fence mismatch"
);
}
assert!(self.publish_multi_node_payload(
descriptor,
4,
&sibling.data,
*sibling_expected_data,
sibling_replacement,
guard,
));
assert!(self.publish_multi_node_payload(
descriptor,
2,
&parent.data,
*parent_expected_data,
parent_replacement,
guard,
));
assert!(self.publish_multi_node_payload(
descriptor,
1,
&node.data,
*expected_data,
source_replacement,
guard,
));
let _ = descriptor.phase.compare_exchange(
OP_FROZEN,
OP_LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
},
OP_LINKED => match &descriptor.kind {
OperationKind::RootReplace {
left_id,
right_id,
root_id,
} => {
self.node(*left_id).compare_parent(None, Some(*root_id));
self.node(*right_id).compare_parent(None, Some(*root_id));
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::RootCollapse {
expected_version,
child_id,
..
} => {
self.node(*child_id).compare_parent(Some(node_id), None);
self.finish_frozen_version(node, *expected_version);
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::LeafSplit {
expected_version,
old_high,
separator,
right_id,
root_id,
needs_root,
..
} => {
let _ = node.high_key.compare_exchange(
*old_high,
*separator,
Ordering::AcqRel,
Ordering::Acquire,
);
self.finish_frozen_version(node, *expected_version);
let parented = self.finish_split_parent(
node_id,
*separator,
right_id,
root_id,
*needs_root,
guard,
);
if parented {
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
OperationKind::ParentInsert {
expected_version,
right_id,
..
} => {
self.node(*right_id).compare_parent(None, Some(node_id));
self.finish_frozen_version(node, *expected_version);
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::InternalSplit {
expected_version,
old_high,
separator,
right_id,
root_id,
needs_root,
..
} => {
let _ = node.high_key.compare_exchange(
*old_high,
*separator,
Ordering::AcqRel,
Ordering::Acquire,
);
self.finish_frozen_version(node, *expected_version);
if self.finish_split_parent(
node_id,
*separator,
right_id,
root_id,
*needs_root,
guard,
) {
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
OperationKind::LogicalRemove {
expected_version, ..
}
| OperationKind::LeafUpsert {
expected_version, ..
} => {
self.finish_frozen_version(node, *expected_version);
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::Redirect {
expected_version, ..
} => {
self.finish_frozen_version(node, *expected_version);
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::LeftRedirect {
expected_version,
left_id,
left_expected_version,
parent_id,
parent_expected_version,
moved_children,
..
} => {
node.compare_parent(Some(*parent_id), None);
for child_id in moved_children.iter().copied() {
let child = self.node(child_id);
let current = child.parent();
if current == Some(node_id) || current.is_none() {
child.compare_parent(current, Some(*left_id));
}
}
self.finish_frozen_version(&self.node(*left_id), *left_expected_version);
self.finish_frozen_version(
&self.node(*parent_id),
*parent_expected_version,
);
self.finish_frozen_version(node, *expected_version);
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::RightRedirect {
expected_version,
right_id,
right_expected_version,
parent_id,
parent_expected_version,
moved_children,
..
} => {
node.compare_parent(Some(*parent_id), None);
for child_id in moved_children.iter().copied() {
let child = self.node(child_id);
let current = child.parent();
if current == Some(node_id) || current.is_none() {
child.compare_parent(current, Some(*right_id));
}
}
self.finish_frozen_version(&self.node(*right_id), *right_expected_version);
self.finish_frozen_version(
&self.node(*parent_id),
*parent_expected_version,
);
self.finish_frozen_version(node, *expected_version);
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OperationKind::InternalRedistribute {
expected_version,
sibling_id,
sibling_expected_version,
parent_id,
parent_expected_version,
moved_children,
..
} => {
for child_id in moved_children.iter().copied() {
let child = self.node(child_id);
let current = child.parent();
if current == Some(*sibling_id) || current.is_none() {
child.compare_parent(current, Some(node_id));
}
}
self.finish_frozen_version(
&self.node(*sibling_id),
*sibling_expected_version,
);
self.finish_frozen_version(
&self.node(*parent_id),
*parent_expected_version,
);
self.finish_frozen_version(node, *expected_version);
let _ = descriptor.phase.compare_exchange(
OP_LINKED,
OP_PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
},
OP_PARENTED => {
let _ = descriptor.phase.compare_exchange(
OP_PARENTED,
OP_DONE,
Ordering::AcqRel,
Ordering::Acquire,
);
}
OP_DONE | OP_ABORTED => {
let aborted = descriptor.phase.load(Ordering::Acquire) == OP_ABORTED;
if let OperationKind::LeftRedirect {
source_id,
expected_data,
left_id,
left_expected_data,
left_replacement_data,
parent_id,
parent_expected_data,
parent_replacement_data,
..
} = &descriptor.kind
{
let left = self.node(*left_id);
let parent = self.node(*parent_id);
let _ = left.operation.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
);
let _ = parent.operation.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
);
let source = self.node(*source_id);
if source
.operation
.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
)
.is_ok()
{
if aborted {
self.operation_aborts.fetch_add(1, Ordering::Relaxed);
}
let replaced = descriptor.payload_replaced.load(Ordering::Acquire);
let source_replacement =
descriptor.replacement_data.load(Ordering::Acquire);
if replaced & 1 != 0 {
let expected = Shared::from(*expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if source_replacement != 0 {
unsafe {
drop(Box::from_raw(source_replacement as *mut NodePayload))
};
}
let parent_replacement =
parent_replacement_data.load(Ordering::Acquire);
if replaced & 2 != 0 {
let expected =
Shared::from(*parent_expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if parent_replacement != 0 {
unsafe {
drop(Box::from_raw(parent_replacement as *mut NodePayload))
};
}
let left_replacement = left_replacement_data.load(Ordering::Acquire);
if replaced & 4 != 0 {
let expected =
Shared::from(*left_expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if left_replacement != 0 {
unsafe {
drop(Box::from_raw(left_replacement as *mut NodePayload))
};
}
unsafe { guard.defer_destroy(operation) };
if !aborted {
self.retire_node(*source_id, guard);
if !self.try_collapse_root(*parent_id, guard) {
self.try_publish_internal_redirect(*parent_id, guard);
}
}
}
return;
}
if let OperationKind::RightRedirect {
source_id,
expected_data,
right_id,
right_expected_data,
right_replacement_data,
parent_id,
parent_expected_data,
parent_replacement_data,
..
} = &descriptor.kind
{
#[cfg(test)]
if PAUSE_RIGHT_REDIRECT_BEFORE_SPLICE.get() {
return;
}
let right = self.node(*right_id);
let parent = self.node(*parent_id);
let _ = right.operation.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
);
let _ = parent.operation.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
);
if !aborted {
self.splice_internal_predecessor(*source_id, *right_id, guard);
}
let source = self.node(*source_id);
if source
.operation
.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
)
.is_ok()
{
if aborted {
self.operation_aborts.fetch_add(1, Ordering::Relaxed);
}
let replaced = descriptor.payload_replaced.load(Ordering::Acquire);
let source_replacement =
descriptor.replacement_data.load(Ordering::Acquire);
if replaced & 1 != 0 {
let expected = Shared::from(*expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if source_replacement != 0 {
unsafe {
drop(Box::from_raw(source_replacement as *mut NodePayload))
};
}
let parent_replacement =
parent_replacement_data.load(Ordering::Acquire);
if replaced & 2 != 0 {
let expected =
Shared::from(*parent_expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if parent_replacement != 0 {
unsafe {
drop(Box::from_raw(parent_replacement as *mut NodePayload))
};
}
let right_replacement = right_replacement_data.load(Ordering::Acquire);
if replaced & 4 != 0 {
let expected =
Shared::from(*right_expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if right_replacement != 0 {
unsafe {
drop(Box::from_raw(right_replacement as *mut NodePayload))
};
}
unsafe { guard.defer_destroy(operation) };
if !aborted {
self.retire_node(*source_id, guard);
if !self.try_collapse_root(*parent_id, guard) {
self.try_publish_internal_redirect(*parent_id, guard);
}
}
}
return;
}
if let OperationKind::InternalRedistribute {
source_id,
expected_data,
sibling_id,
sibling_expected_data,
sibling_replacement_data,
parent_id,
parent_expected_data,
parent_replacement_data,
..
} = &descriptor.kind
{
let sibling = self.node(*sibling_id);
let parent = self.node(*parent_id);
let _ = sibling.operation.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
);
let _ = parent.operation.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
);
let source = self.node(*source_id);
if source
.operation
.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
)
.is_ok()
{
if aborted {
self.operation_aborts.fetch_add(1, Ordering::Relaxed);
}
let replaced = descriptor.payload_replaced.load(Ordering::Acquire);
let source_replacement =
descriptor.replacement_data.load(Ordering::Acquire);
if replaced & 1 != 0 {
let expected = Shared::from(*expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if source_replacement != 0 {
unsafe {
drop(Box::from_raw(source_replacement as *mut NodePayload))
};
}
let parent_replacement =
parent_replacement_data.load(Ordering::Acquire);
if replaced & 2 != 0 {
let expected =
Shared::from(*parent_expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if parent_replacement != 0 {
unsafe {
drop(Box::from_raw(parent_replacement as *mut NodePayload))
};
}
let sibling_replacement =
sibling_replacement_data.load(Ordering::Acquire);
if replaced & 4 != 0 {
let expected =
Shared::from(*sibling_expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
} else if sibling_replacement != 0 {
unsafe {
drop(Box::from_raw(sibling_replacement as *mut NodePayload))
};
}
unsafe { guard.defer_destroy(operation) };
}
return;
}
if node
.operation
.compare_exchange(
operation,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
guard,
)
.is_ok()
{
if aborted {
self.operation_aborts.fetch_add(1, Ordering::Relaxed);
}
if descriptor.payload_replaced.load(Ordering::Acquire) != 0 {
let expected_data = match &descriptor.kind {
OperationKind::LeafSplit { expected_data, .. }
| OperationKind::ParentInsert { expected_data, .. }
| OperationKind::InternalSplit { expected_data, .. } => {
Some(*expected_data)
}
OperationKind::LogicalRemove { expected_data, .. } => {
Some(*expected_data)
}
OperationKind::LeafUpsert { expected_data, .. } => {
Some(*expected_data)
}
OperationKind::Redirect { expected_data, .. } => {
Some(*expected_data)
}
OperationKind::RootReplace { .. } => None,
OperationKind::LeftRedirect { .. } => None,
OperationKind::RightRedirect { .. } => None,
OperationKind::InternalRedistribute { .. } => None,
OperationKind::RootCollapse { expected_data, .. } => {
Some(*expected_data)
}
};
if let Some(expected_data) = expected_data {
let expected = Shared::from(expected_data as *const NodePayload);
unsafe { guard.defer_destroy(expected) };
}
}
unsafe { guard.defer_destroy(operation) };
if !aborted {
match &descriptor.kind {
OperationKind::RootCollapse { .. } => {
self.retire_node(node_id, guard);
}
OperationKind::Redirect { .. }
if self.find_leaf_predecessor(node_id, guard).is_none() =>
{
self.retire_node(node_id, guard);
}
_ => {}
}
}
}
return;
}
_ => unreachable!("invalid B+ operation phase"),
}
}
}
}
impl TreeNode {
fn new(
parent: Option<NodeId>,
right_sibling: Option<NodeId>,
high_key: usize,
data: NodeData,
) -> Self {
#[cfg(test)]
assert_payload_fence(&data, high_key, "new B+ node");
Self {
parent: AtomicUsize::new(parent.unwrap_or(NO_NODE)),
right_sibling: AtomicUsize::new(right_sibling.unwrap_or(NO_NODE)),
high_key: AtomicUsize::new(high_key),
version: AtomicU64::new(0),
operation: Atomic::null(),
data: Atomic::new(NodePayload::new(high_key, data, "new B+ node")),
payload_slabs: AtomicPtr::new(std::ptr::null_mut()),
}
}
fn attach_payload_slabs(&mut self, slabs: &PayloadSlabs) {
self.payload_slabs.store(
slabs as *const PayloadSlabs as *mut PayloadSlabs,
Ordering::Release,
);
let guard = unsafe { unprotected() };
let current = self.data.swap(Shared::null(), Ordering::Relaxed, guard);
assert!(!current.is_null());
let payload = unsafe { *current.into_owned().into_box() };
self.data
.store(Owned::new(payload.freeze(slabs)), Ordering::Relaxed);
}
fn freeze_payload(&self, payload: NodePayload) -> NodePayload {
let slabs = self.payload_slabs.load(Ordering::Acquire);
assert!(!slabs.is_null(), "TreeNode payload slab was not attached");
payload.freeze(unsafe { &*slabs })
}
fn parent(&self) -> Option<NodeId> {
let parent = self.parent.load(Ordering::Acquire);
(parent != NO_NODE).then_some(parent)
}
#[cfg(test)]
fn set_parent(&self, parent: Option<NodeId>) {
self.parent
.store(parent.unwrap_or(NO_NODE), Ordering::Release);
}
fn compare_parent(&self, expected: Option<NodeId>, parent: Option<NodeId>) -> bool {
let expected = expected.unwrap_or(NO_NODE);
let parent = parent.unwrap_or(NO_NODE);
match self
.parent
.compare_exchange(expected, parent, Ordering::AcqRel, Ordering::Acquire)
{
Ok(_) => true,
Err(actual) => actual == parent,
}
}
#[cfg(test)]
fn lock(&self) -> NodeWriteGuard<'_> {
loop {
if let Some(write) = self.try_lock() {
return write;
}
std::hint::spin_loop();
}
}
#[cfg(test)]
fn try_lock(&self) -> Option<NodeWriteGuard<'_>> {
let version = self.version.load(Ordering::Acquire);
if version & (VERSION_OPERATION_FROZEN | 1) != 0 {
return None;
}
self.version
.compare_exchange(
version,
version.wrapping_add(1),
Ordering::AcqRel,
Ordering::Acquire,
)
.ok()
.map(|_| NodeWriteGuard {
node: self,
version,
})
}
fn data_clone(&self, guard: &Guard) -> NodeData {
let shared = self.data.load(Ordering::Acquire, guard);
unsafe { shared.deref().data.clone() }
}
fn try_read_consistent<R>(
&self,
guard: &Guard,
read: impl FnOnce(usize, &NodeData) -> R,
) -> Option<R> {
let before = self.version.load(Ordering::Acquire);
if before & (VERSION_OPERATION_FROZEN | 1) != 0 {
return None;
}
let shared = self.data.load(Ordering::Acquire, guard);
let payload = unsafe { shared.deref() };
let result = read(payload.high_key, &payload.data);
(self.version.load(Ordering::Acquire) == before).then_some(result)
}
fn compare_publish(
&self,
expected_data: usize,
high_key: usize,
data: NodeData,
origin: &'static str,
guard: &Guard,
) -> bool {
let current = Shared::from(expected_data as *const NodePayload);
#[cfg(test)]
assert_payload_fence(&data, high_key, origin);
let replacement = Owned::new(self.freeze_payload(NodePayload::new(high_key, data, origin)));
match self.data.compare_exchange(
current,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
guard,
) {
Ok(_) => {
unsafe { guard.defer_destroy(current) };
true
}
Err(_) => false,
}
}
#[cfg(test)]
fn publish(&self, data: NodeData, guard: &Guard) -> bool {
let current = self.data.load(Ordering::Acquire, guard);
let high_key = unsafe { current.deref().high_key };
self.compare_publish(
current.as_raw() as usize,
high_key,
data,
"test short B+ writer",
guard,
)
}
#[cfg(test)]
fn publish_with_high(&self, high_key: usize, data: NodeData, guard: &Guard) {
assert_payload_fence(&data, high_key, "test B+ writer");
self.high_key.store(high_key, Ordering::Release);
let previous = self.data.swap(
Owned::new(self.freeze_payload(NodePayload::new(high_key, data, "test B+ writer"))),
Ordering::AcqRel,
guard,
);
unsafe { guard.defer_destroy(previous) };
}
}
impl Drop for TreeNode {
fn drop(&mut self) {
let guard = unsafe { unprotected() };
let current = self.data.swap(Shared::null(), Ordering::Relaxed, guard);
if !current.is_null() {
unsafe { drop(current.into_owned()) };
}
let operation = self
.operation
.swap(Shared::null(), Ordering::Relaxed, guard);
if !operation.is_null() {
unsafe { drop(operation.into_owned()) };
}
}
}
impl AddressTree {
pub fn find_free_fit_near(
&self,
size: usize,
align: usize,
locality: Option<LocalityHint>,
preferred_owner: Option<u64>,
) -> Option<(SpanHandle, usize)> {
let mut best: Option<ScoredFreeFit> = None;
for span in self.values() {
if !span.is_available_free() {
continue;
}
let Some(start) = align_up(span.base, align) else {
continue;
};
let Some(end) = start.checked_add(size) else {
continue;
};
if end > span.base + span.size {
continue;
}
let span_owner = span.owner.load(Ordering::Acquire);
let owner_rank = preferred_owner.map_or(usize::from(span_owner != 0), |owner| {
if span_owner == owner {
0
} else if span_owner == 0 {
1
} else {
2
}
});
let (chunk_rank, distance) = locality.map_or((0, 0), |hint| {
(
usize::from(span.chunk_base != hint.chunk_base),
start.abs_diff(hint.address),
)
});
let score = (owner_rank, chunk_rank, distance);
if best.as_ref().is_none_or(|candidate| score < candidate.2) {
best = Some((span, start, score));
if locality.is_none() && preferred_owner.is_none() {
break;
}
if score == (0, 0, 0) {
break;
}
}
}
best.map(|(span, start, _)| (span, start))
}
pub fn has_pending_free_fit(&self, size: usize, align: usize) -> bool {
self.values().into_iter().any(|span| {
if span.kind() != SpanKind::Free {
return false;
}
let Some(start) = align_up(span.base, align) else {
return false;
};
start
.checked_add(size)
.is_some_and(|end| end <= span.base + span.size)
})
}
}
#[cfg(test)]
struct NodeWriteGuard<'a> {
node: &'a TreeNode,
version: u64,
}
#[cfg(test)]
impl Drop for NodeWriteGuard<'_> {
fn drop(&mut self) {
let held = self.version.wrapping_add(1);
let target = self.version.wrapping_add(2);
let _ =
self.node
.version
.compare_exchange(held, target, Ordering::Release, Ordering::Acquire);
}
}
pub(crate) struct Topology {
pub tree: Arc<AddressTree>,
pub chunks: Vec<ChunkRecord>,
}
impl Topology {
pub fn new() -> Self {
Self {
tree: Arc::new(AddressTree::new()),
chunks: Vec::new(),
}
}
pub fn find_free_fit_near(
&self,
size: usize,
align: usize,
locality: Option<LocalityHint>,
preferred_owner: Option<u64>,
) -> Option<(SpanHandle, usize)> {
self.tree
.find_free_fit_near(size, align, locality, preferred_owner)
}
}
pub(crate) fn align_up(value: usize, align: usize) -> Option<usize> {
debug_assert!(align.is_power_of_two());
value.checked_add(align - 1).map(|v| v & !(align - 1))
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Barrier;
use std::sync::atomic::AtomicBool;
use std::thread;
#[test]
fn epoch_retired_node_slot_waits_for_reader_then_reuses_the_index() {
let collector = Collector::new();
let arena = Arc::new(NodeArena::new());
let id = arena.push(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
)));
let reader_handle = collector.register();
let reader = reader_handle.pin();
let protected = arena
.slot(id)
.unwrap()
.record
.load(Ordering::Acquire, &reader);
assert!(!protected.is_null());
let writer_handle = collector.register();
let writer = writer_handle.pin();
assert!(arena.retire_later(id, &writer));
drop(writer);
for _ in 0..16 {
writer_handle.pin().flush();
}
assert_eq!(arena.live(), 1, "pinned reader must delay slot clearing");
let old_node = unsafe { protected.deref() }.node.clone();
assert_eq!(old_node.high_key.load(Ordering::Acquire), usize::MAX);
drop(reader);
for _ in 0..128 {
let guard = writer_handle.pin();
guard.flush();
drop(guard);
if arena.live() == 0 {
break;
}
}
assert_eq!(arena.live(), 0);
assert_eq!(arena.retired(), 1);
let reused = arena.push(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
)));
assert_eq!(reused, id);
assert_eq!(arena.reused(), 1);
assert_eq!(arena.len(), 1);
}
#[test]
fn typed_tree_node_slab_waits_for_last_handle_then_reuses_slot() {
let slab = TreeNodeSlabOwner::new();
let first = slab.allocate(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
));
let first_slot = first.slot;
let protected = first.clone();
drop(first);
assert_eq!(slab.live.load(Ordering::Relaxed), 1);
let second = slab.allocate(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
));
assert_ne!(second.slot, first_slot);
assert_eq!(slab.next.load(Ordering::Relaxed), 2);
drop(protected);
let reused = slab.allocate(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
));
assert_eq!(reused.slot, first_slot);
assert_eq!(slab.reused.load(Ordering::Relaxed), 1);
assert_eq!(slab.allocated_blocks(), 1);
assert_eq!(reused.slot.as_ptr() as usize % TREE_NODE_SLOT_BYTES, 0);
drop(second);
drop(reused);
assert_eq!(slab.live.load(Ordering::Relaxed), 0);
}
#[test]
fn concurrent_node_segments_share_vm_metadata_blocks() {
const THREADS: usize = 8;
const NODES_PER_THREAD: usize = 64;
let arena = Arc::new(NodeArena::new());
let start = Arc::new(Barrier::new(THREADS));
let mut workers = Vec::new();
for _ in 0..THREADS {
let arena = Arc::clone(&arena);
let start = Arc::clone(&start);
workers.push(thread::spawn(move || {
start.wait();
(0..NODES_PER_THREAD)
.map(|_| {
arena.push(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
)))
})
.collect::<Vec<_>>()
}));
}
let ids = workers
.into_iter()
.flat_map(|worker| worker.join().unwrap())
.collect::<Vec<_>>();
assert_eq!(ids.len(), THREADS * NODES_PER_THREAD);
assert_eq!(arena.len(), ids.len());
assert_eq!(arena.allocated_segments(), 2);
assert_eq!(arena.allocated_metadata_blocks(), 2);
let first = arena.published_segment(0) as usize;
let second = arena.published_segment(1) as usize;
assert_eq!(first % NODE_SEGMENT_BYTES, 0);
assert_eq!(second - first, NODE_ARENA_SEGMENT_BYTES);
let collector = Collector::new();
let handle = collector.register();
let guard = handle.pin();
for id in ids {
assert_eq!(
arena.get(id, &guard).high_key.load(Ordering::Acquire),
usize::MAX
);
}
}
fn find_cross_parent_boundary(
tree: &AddressTree,
) -> (NodeId, NodeId, NodeId, NodeId, usize, Vec<usize>) {
let handle = tree.collector.register();
let guard = handle.pin();
let mut source_id = 0;
while source_id != NO_NODE {
let source = tree.node(source_id);
let right_id = source.right_sibling.load(Ordering::Acquire);
if right_id == NO_NODE {
break;
}
let Some(parent_id) = tree.resolve_parent(source_id, &source, &guard) else {
source_id = right_id;
continue;
};
let right = tree.node(right_id);
let right_parent = tree.resolve_parent(right_id, &right, &guard);
let candidate = tree.read_node(parent_id, &tree.node(parent_id), &guard, |_, data| {
let NodeData::Internal { children, .. } = data else {
return None;
};
let position = children.iter().position(|child| *child == source_id)?;
if right_parent != Some(parent_id) && position > 0 {
Some(children[position - 1])
} else {
None
}
});
if let Some(left_id) = candidate {
if let Some((source_high, keys)) =
tree.read_node(source_id, &source, &guard, |high, data| match data {
NodeData::Leaf { entries } => Some((
high,
entries.iter().map(|entry| entry.0).collect::<Vec<_>>(),
)),
_ => None,
})
{
return (source_id, parent_id, left_id, right_id, source_high, keys);
}
}
source_id = right_id;
}
panic!("multi-level tree must contain a cross-parent leaf boundary")
}
fn find_first_child_with_global_predecessor(
tree: &AddressTree,
) -> (NodeId, NodeId, NodeId, NodeId, Vec<usize>) {
let handle = tree.collector.register();
let guard = handle.pin();
let mut previous = None;
let mut source_id = 0;
while source_id != NO_NODE {
let source = tree.node_guarded(source_id, &guard);
let right_id = source.right_sibling.load(Ordering::Acquire);
if let (Some(left_id), Some(parent_id)) =
(previous, tree.resolve_parent(source_id, &source, &guard))
{
let first = tree.read_node(
parent_id,
&tree.node_guarded(parent_id, &guard),
&guard,
|_, data| match data {
NodeData::Internal { children, .. } => {
children.len() > 1 && children.first() == Some(&source_id)
}
_ => false,
},
);
if first && right_id != NO_NODE {
let keys = tree.read_node(source_id, &source, &guard, |_, data| match data {
NodeData::Leaf { entries } => {
entries.iter().map(|entry| entry.0).collect::<Vec<_>>()
}
_ => Vec::new(),
});
if !keys.is_empty() {
return (source_id, parent_id, left_id, right_id, keys);
}
}
}
previous = Some(source_id);
source_id = right_id;
}
panic!("multi-level tree must contain a first-child leaf with a predecessor")
}
fn build_redistribution_fixture(
source_first: bool,
) -> (AddressTree, NodeId, NodeId, NodeId, Vec<usize>) {
const CHILDREN: usize = FANOUT + 2;
let tree = AddressTree::new();
let chunk = 0x10_0000;
let bases = (0..CHILDREN)
.map(|index| chunk + index * 4096)
.collect::<Vec<_>>();
let handle = tree.collector.register();
let guard = handle.pin();
let first = tree.node(0);
{
let _write = first.lock();
first.publish_with_high(
bases[1],
NodeData::Leaf {
entries: vec![(
bases[0],
tree.allocate_span(SpanDesc::free(bases[0], 4096, chunk)),
)]
.into(),
},
&guard,
);
}
first.right_sibling.store(1, Ordering::Release);
for index in 1..CHILDREN {
let right = (index + 1 < CHILDREN).then_some(index + 1);
let high = right.map_or(usize::MAX, |next| bases[next]);
assert_eq!(
tree.append_node(Arc::new(TreeNode::new(
None,
right,
high,
NodeData::Leaf {
entries: vec![(
bases[index],
tree.allocate_span(SpanDesc::free(bases[index], 4096, chunk)),
)]
.into(),
},
))),
index
);
}
let (source_id, sibling_id) = if source_first {
let source_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
bases[1],
NodeData::Internal {
keys: Vec::new().into(),
children: vec![0].into(),
},
)));
let sibling_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: bases[2..].to_vec().into(),
children: (1..CHILDREN).collect(),
},
)));
tree.node(source_id)
.right_sibling
.store(sibling_id, Ordering::Release);
for child in 1..CHILDREN {
tree.node(child).set_parent(Some(sibling_id));
}
tree.node(0).set_parent(Some(source_id));
(source_id, sibling_id)
} else {
let sibling_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
bases[FANOUT + 1],
NodeData::Internal {
keys: bases[1..FANOUT + 1].to_vec().into(),
children: (0..FANOUT + 1).collect(),
},
)));
let source_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: Vec::new().into(),
children: vec![FANOUT + 1].into(),
},
)));
tree.node(sibling_id)
.right_sibling
.store(source_id, Ordering::Release);
for child in 0..FANOUT + 1 {
tree.node(child).set_parent(Some(sibling_id));
}
tree.node(FANOUT + 1).set_parent(Some(source_id));
(source_id, sibling_id)
};
let separator = if source_first {
bases[1]
} else {
bases[FANOUT + 1]
};
let root_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![separator].into(),
children: (if source_first {
vec![source_id, sibling_id]
} else {
vec![sibling_id, source_id]
})
.into(),
},
)));
tree.node(source_id).set_parent(Some(root_id));
tree.node(sibling_id).set_parent(Some(root_id));
tree.root.store(root_id, Ordering::Release);
drop(guard);
(tree, source_id, sibling_id, root_id, bases)
}
fn build_cross_parent_right_redirect_fixture()
-> (AddressTree, NodeId, NodeId, NodeId, Vec<usize>) {
let tree = AddressTree::new();
let chunk = 0x10_0000;
let bases = (0..4).map(|index| chunk + index * 4096).collect::<Vec<_>>();
let handle = tree.collector.register();
let guard = handle.pin();
{
let first = tree.node(0);
let _write = first.lock();
first.publish_with_high(
bases[1],
NodeData::Leaf {
entries: vec![(
bases[0],
tree.allocate_span(SpanDesc::free(bases[0], 4096, chunk)),
)]
.into(),
},
&guard,
);
}
let mut leaves = vec![0];
for index in 1..bases.len() {
let leaf = tree.append_node(Arc::new(TreeNode::new(
None,
None,
bases.get(index + 1).copied().unwrap_or(usize::MAX),
NodeData::Leaf {
entries: vec![(
bases[index],
tree.allocate_span(SpanDesc::free(bases[index], 4096, chunk)),
)]
.into(),
},
)));
tree.node(*leaves.last().unwrap())
.right_sibling
.store(leaf, Ordering::Release);
leaves.push(leaf);
}
let left_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
bases[1],
NodeData::Internal {
keys: Vec::new().into(),
children: vec![leaves[0]].into(),
},
)));
let source_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
bases[2],
NodeData::Internal {
keys: Vec::new().into(),
children: vec![leaves[1]].into(),
},
)));
let right_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![bases[3]].into(),
children: vec![leaves[2], leaves[3]].into(),
},
)));
tree.node(left_id)
.right_sibling
.store(source_id, Ordering::Release);
tree.node(source_id)
.right_sibling
.store(right_id, Ordering::Release);
let left_parent = tree.append_node(Arc::new(TreeNode::new(
None,
None,
bases[1],
NodeData::Internal {
keys: Vec::new().into(),
children: vec![left_id].into(),
},
)));
let source_parent = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![bases[2]].into(),
children: vec![source_id, right_id].into(),
},
)));
tree.node(left_parent)
.right_sibling
.store(source_parent, Ordering::Release);
let root = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![bases[1]].into(),
children: vec![left_parent, source_parent].into(),
},
)));
for (child, parent) in [
(leaves[0], left_id),
(leaves[1], source_id),
(leaves[2], right_id),
(leaves[3], right_id),
(left_id, left_parent),
(source_id, source_parent),
(right_id, source_parent),
(left_parent, root),
(source_parent, root),
] {
tree.node(child).set_parent(Some(parent));
}
tree.root.store(root, Ordering::Release);
drop(guard);
(tree, source_id, left_id, right_id, bases)
}
#[test]
fn bplus_tree_splits_internal_nodes_and_preserves_lookup() {
let tree = AddressTree::new();
for index in (0..500).rev() {
let base = 0x10000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10000)),
);
}
tree.validate().unwrap();
assert_eq!(tree.values().len(), 500);
for index in 0..500 {
let base = 0x10000 + index * 4096;
assert_eq!(tree.get(base).unwrap().base, base);
assert_eq!(tree.containing(base + 17).unwrap().base, base);
}
}
#[test]
fn reader_helps_a_paused_root_replacement_to_completion() {
let tree = Arc::new(AddressTree::new());
let left = tree.node(0);
let handle = tree.collector.register();
let guard = handle.pin();
let left_span = tree.allocate_span(SpanDesc::free(0x10_0000, 4096, 0x10_0000));
let right_span = tree.allocate_span(SpanDesc::free(0x20_0000, 4096, 0x10_0000));
{
let _write = left.lock();
left.publish_with_high(
right_span.base,
NodeData::Leaf {
entries: vec![(left_span.base, left_span.clone())].into(),
},
&guard,
);
}
let right_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: vec![(right_span.base, right_span.clone())].into(),
},
)));
left.right_sibling.store(right_id, Ordering::Release);
let root_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![right_span.base].into(),
children: vec![0, right_id].into(),
},
)));
left.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: 0,
kind: OperationKind::RootReplace {
left_id: 0,
right_id,
root_id,
},
}),
Ordering::Release,
);
drop(guard);
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(0x20_0000).unwrap().base);
assert_eq!(helper.join().unwrap(), 0x20_0000);
assert_eq!(tree.root.load(Ordering::Acquire), root_id);
assert_eq!(tree.node(0).parent(), Some(root_id));
assert_eq!(tree.node(right_id).parent(), Some(root_id));
tree.validate().unwrap();
}
#[test]
fn batch_replacement_publishes_one_complete_leaf_payload() {
let tree = AddressTree::new();
let base = 0x10_0000;
let source = tree.allocate_span(SpanDesc::free(base, 0x10_000, base));
tree.insert(base, source.clone());
let replacements = (0..4)
.map(|index| {
let replacement_base = base + index * 0x4_000;
tree.allocate_span(SpanDesc::free(replacement_base, 0x4_000, base))
})
.collect::<Vec<_>>();
assert!(tree.replace_batch(&source, &replacements));
assert_eq!(tree.values().len(), replacements.len());
for replacement in &replacements {
assert!(SpanHandle::ptr_eq(
&tree.get(replacement.base).unwrap(),
replacement
));
}
let stats = tree.operation_stats();
assert_eq!(stats.batch_replacements, 1);
assert_eq!(stats.logical_removes, 0);
tree.validate().unwrap();
}
#[test]
fn batch_replacement_routes_a_coalesced_extent_across_an_old_leaf_fence() {
let tree = AddressTree::new();
let chunk = 0x10_0000;
let fence = chunk + 0x20_000;
let source = tree.allocate_span(SpanDesc::free(chunk, 0x90_000, chunk));
let outside = tree.allocate_span(SpanDesc::free(chunk + 0x90_000, 0x10_000, chunk));
let left = tree.node(0);
tree.with_guard(|guard| {
let _write = left.lock();
left.publish_with_high(
fence,
NodeData::Leaf {
entries: vec![(source.base, source.clone())].into(),
},
guard,
);
let right_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: vec![(outside.base, outside.clone())].into(),
},
)));
left.right_sibling.store(right_id, Ordering::Release);
let root_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![fence].into(),
children: vec![0, right_id].into(),
},
)));
left.set_parent(Some(root_id));
tree.node(right_id).set_parent(Some(root_id));
tree.root.store(root_id, Ordering::Release);
});
let replacements = (0..9)
.map(|index| {
let base = chunk + index * 0x10_000;
tree.allocate_span(SpanDesc::free(base, 0x10_000, chunk))
})
.collect::<Vec<_>>();
assert!(tree.replace_batch(&source, &replacements));
assert_eq!(tree.values().len(), replacements.len() + 1);
for replacement in &replacements {
assert!(SpanHandle::ptr_eq(
&tree.get(replacement.base).unwrap(),
replacement
));
}
assert!(SpanHandle::ptr_eq(
&tree.get(outside.base).unwrap(),
&outside
));
tree.validate().unwrap();
}
#[test]
fn batch_replacement_uses_helpable_split_when_leaf_overflows() {
let tree = AddressTree::new();
let chunk = 0x10_0000;
let mut source = None;
for index in 0..FANOUT {
let base = chunk + index * 0x10_000;
let span = tree.allocate_span(SpanDesc::free(base, 0x10_000, chunk));
if index == 10 {
source = Some(span.clone());
}
tree.insert(base, span);
}
let source = source.unwrap();
let replacements = (0..8)
.map(|index| {
let base = source.base + index * 0x2_000;
tree.allocate_span(SpanDesc::free(base, 0x2_000, chunk))
})
.collect::<Vec<_>>();
assert!(tree.replace_batch(&source, &replacements));
assert_eq!(tree.values().len(), FANOUT - 1 + replacements.len());
assert_eq!(tree.operation_stats().batch_replacements, 1);
assert_eq!(tree.operation_stats().leaf_splits, 1);
for replacement in replacements {
assert_eq!(tree.get(replacement.base).unwrap().base, replacement.base);
}
tree.validate().unwrap();
}
#[test]
fn concurrent_batch_replacement_has_one_winner() {
let tree = Arc::new(AddressTree::new());
let base = 0x10_0000;
let source = tree.allocate_span(SpanDesc::free(base, 0x10_000, base));
tree.insert(base, source.clone());
let first = tree.allocate_span(SpanDesc::free(base, 0x10_000, base));
let second = tree.allocate_span(SpanDesc::free(base, 0x10_000, base));
let barrier = Arc::new(Barrier::new(3));
let mut writers = Vec::new();
for replacement in [first.clone(), second.clone()] {
let tree = Arc::clone(&tree);
let source = source.clone();
let barrier = Arc::clone(&barrier);
writers.push(thread::spawn(move || {
barrier.wait();
(
tree.replace_batch(&source, std::slice::from_ref(&replacement)),
replacement,
)
}));
}
barrier.wait();
let results = writers
.into_iter()
.map(|writer| writer.join().unwrap())
.collect::<Vec<_>>();
assert_eq!(results.iter().filter(|result| result.0).count(), 1);
let winner = &results.iter().find(|result| result.0).unwrap().1;
assert!(SpanHandle::ptr_eq(&tree.get(base).unwrap(), winner));
tree.validate().unwrap();
}
#[test]
fn concurrent_batch_replacements_preserve_multilevel_order() {
const THREADS: usize = 8;
const SOURCES: usize = 1024;
const PARTS: usize = 4;
let tree = Arc::new(AddressTree::new());
let chunk = 0x10_0000;
let sources = (0..SOURCES)
.map(|index| {
let base = chunk + index * 0x10_000;
let source = tree.allocate_span(SpanDesc::free(base, 0x10_000, chunk));
tree.insert(base, source.clone());
source
})
.collect::<Vec<_>>();
let barrier = Arc::new(Barrier::new(THREADS));
let mut workers = Vec::new();
for thread_index in 0..THREADS {
let tree = Arc::clone(&tree);
let barrier = Arc::clone(&barrier);
let sources = sources.clone();
workers.push(thread::spawn(move || {
barrier.wait();
for index in (thread_index..SOURCES).step_by(THREADS) {
let source = &sources[index];
let replacements = (0..PARTS)
.map(|part| {
let base = source.base + part * 0x4_000;
tree.allocate_span(SpanDesc::free(base, 0x4_000, chunk))
})
.collect::<Vec<_>>();
assert!(tree.replace_batch(source, &replacements));
}
}));
}
for worker in workers {
worker.join().unwrap();
}
tree.validate().unwrap();
assert_eq!(tree.values().len(), SOURCES * PARTS);
assert_eq!(tree.operation_stats().batch_replacements, SOURCES as u64);
for source in sources {
for part in 0..PARTS {
let base = source.base + part * 0x4_000;
assert_eq!(tree.get(base).unwrap().base, base);
}
}
}
#[test]
fn reader_helps_a_paused_leaf_split_to_completion() {
let tree = Arc::new(AddressTree::new());
for index in 0..FANOUT {
let base = 0x10_0000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
let leaf_id = tree.root.load(Ordering::Acquire);
let leaf = tree.node(leaf_id);
let handle = tree.collector.register();
let guard = handle.pin();
let (expected_version, expected_data, _expected_high, mut left_data) =
tree.read_node_snapshot(leaf_id, &leaf, &guard);
let new_base = 0x10_0000 + FANOUT * 4096;
let NodeData::Leaf { entries } = &mut left_data else {
panic!("unsplit root must still be a leaf");
};
entries.push((
new_base,
tree.allocate_span(SpanDesc::free(new_base, 4096, 0x10_0000)),
));
let right_entries = entries.split_off(entries.len() / 2);
let separator = right_entries[0].0;
leaf.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: separator,
kind: OperationKind::LeafSplit {
expected_version,
expected_data,
old_right: NO_NODE,
old_high: usize::MAX,
separator,
right_id: AtomicUsize::new(NO_NODE),
root_id: AtomicUsize::new(NO_NODE),
needs_root: true,
left_data,
right_data: NodeData::Leaf {
entries: right_entries,
},
},
}),
Ordering::Release,
);
drop(guard);
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(new_base).unwrap().base);
assert_eq!(helper.join().unwrap(), new_base);
assert_eq!(tree.values().len(), FANOUT + 1);
assert!(
leaf.operation
.load(Ordering::Acquire, unsafe { unprotected() })
.is_null()
);
tree.validate().unwrap();
}
#[test]
fn reader_helps_a_paused_logical_remove_to_completion() {
let tree = Arc::new(AddressTree::new());
let bases = [0x10_0000, 0x11_0000, 0x12_0000];
for base in bases {
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
let target = bases[1];
let handle = tree.collector.register();
let guard = handle.pin();
let leaf_id = tree.find_leaf(target, &guard);
let leaf = tree.node(leaf_id);
let (expected_version, expected_data, expected_high, mut new_data) =
tree.read_node_snapshot(leaf_id, &leaf, &guard);
let NodeData::Leaf { entries } = &mut new_data else {
panic!("target must resolve to a leaf");
};
let position = entries
.binary_search_by_key(&target, |entry| entry.0)
.unwrap();
entries.remove(position);
leaf.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind: OperationKind::LogicalRemove {
expected_version,
expected_data,
new_data,
},
}),
Ordering::Release,
);
drop(guard);
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(target).is_none());
assert!(helper.join().unwrap());
assert_eq!(tree.get(bases[0]).unwrap().base, bases[0]);
assert_eq!(tree.get(bases[2]).unwrap().base, bases[2]);
assert!(
leaf.operation
.load(Ordering::Acquire, unsafe { unprotected() })
.is_null()
);
tree.validate().unwrap();
}
#[test]
fn reader_helps_a_paused_empty_leaf_upsert_to_completion() {
let tree = Arc::new(AddressTree::new());
let key = 0x10_0000;
let leaf_id = 0;
let leaf = tree.node(leaf_id);
let handle = tree.collector.register();
let guard = handle.pin();
let (expected_version, expected_data, expected_high, _) =
tree.read_node_snapshot(leaf_id, &leaf, &guard);
leaf.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind: OperationKind::LeafUpsert {
expected_version,
expected_data,
new_data: NodeData::Leaf {
entries: vec![(
key,
tree.allocate_span(SpanDesc::free(key, 4096, 0x10_0000)),
)]
.into(),
},
},
}),
Ordering::Release,
);
drop(guard);
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(key).unwrap().base);
assert_eq!(helper.join().unwrap(), key);
assert!(
leaf.operation
.load(Ordering::Acquire, unsafe { unprotected() })
.is_null()
);
tree.validate().unwrap();
}
#[test]
fn paused_cas_upsert_does_not_block_another_writer() {
let tree = AddressTree::new();
let first = 0x10_0000;
let paused = 0x11_0000;
let concurrent = 0x12_0000;
tree.insert(
first,
tree.allocate_span(SpanDesc::free(first, 4096, 0x10_0000)),
);
let leaf = tree.node(0);
let handle = tree.collector.register();
let guard = handle.pin();
let (_, expected_data, high_key, mut candidate) = tree.read_node_snapshot(0, &leaf, &guard);
let NodeData::Leaf { entries } = &mut candidate else {
panic!("root must still be a leaf");
};
entries.push((
paused,
tree.allocate_span(SpanDesc::free(paused, 4096, 0x10_0000)),
));
let stable_version = leaf.version.load(Ordering::Acquire);
tree.insert(
concurrent,
tree.allocate_span(SpanDesc::free(concurrent, 4096, 0x10_0000)),
);
assert_eq!(leaf.version.load(Ordering::Acquire), stable_version);
assert!(!leaf.compare_publish(
expected_data,
high_key,
candidate,
"paused CAS upsert",
&guard,
));
drop(guard);
tree.insert(
paused,
tree.allocate_span(SpanDesc::free(paused, 4096, 0x10_0000)),
);
assert_eq!(tree.get(first).unwrap().base, first);
assert_eq!(tree.get(paused).unwrap().base, paused);
assert_eq!(tree.get(concurrent).unwrap().base, concurrent);
tree.validate().unwrap();
}
#[test]
fn concurrent_logical_remove_has_one_winner() {
let tree = Arc::new(AddressTree::new());
let target = 0x10_0000;
tree.insert(
target,
tree.allocate_span(SpanDesc::free(target, 4096, 0x10_0000)),
);
let barrier = Arc::new(std::sync::Barrier::new(3));
let mut removers = Vec::new();
for _ in 0..2 {
let tree = Arc::clone(&tree);
let barrier = Arc::clone(&barrier);
removers.push(thread::spawn(move || {
barrier.wait();
tree.remove(target).is_some()
}));
}
barrier.wait();
let winners = removers
.into_iter()
.map(|remover| remover.join().unwrap())
.filter(|removed| *removed)
.count();
assert_eq!(winners, 1);
assert!(tree.get(target).is_none());
tree.validate().unwrap();
}
#[test]
fn empty_non_right_leaf_redirects_and_accepts_lower_reinsertion() {
let tree = AddressTree::new();
let bases = (0..=FANOUT)
.map(|index| 0x10_0000 + index * 4096)
.collect::<Vec<_>>();
for base in bases.iter().copied() {
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
let left = tree.node(0);
let handle = tree.collector.register();
let guard = handle.pin();
let left_keys = tree.read_node(0, &left, &guard, |_, data| match data {
NodeData::Leaf { entries } => entries.iter().map(|entry| entry.0).collect::<Vec<_>>(),
_ => panic!("first split child must be a leaf"),
});
let target = left.right_sibling.load(Ordering::Acquire);
assert_ne!(target, NO_NODE);
drop(guard);
for key in left_keys.iter().copied() {
assert!(tree.remove(key).is_some());
}
let handle = tree.collector.register();
let guard = handle.pin();
tree.read_node(0, &left, &guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target: actual } if *actual == target));
});
drop(guard);
let reinserted = left_keys[left_keys.len() / 2];
tree.insert(
reinserted,
tree.allocate_span(SpanDesc::free(reinserted, 4096, 0x10_0000)),
);
assert_eq!(tree.get(reinserted).unwrap().base, reinserted);
assert_eq!(tree.root.load(Ordering::Acquire), target);
assert_eq!(tree.node(target).parent(), None);
let stats = tree.operation_stats();
assert_eq!(stats.redirects, 1);
assert_eq!(stats.root_collapses, 1);
tree.validate().unwrap();
}
#[test]
fn cross_parent_empty_leaf_splices_into_its_left_parent_range() {
const KEYS: usize = FANOUT * FANOUT;
let tree = AddressTree::new();
let chunk = 0x10_0000;
for index in 0..KEYS {
let base = chunk + index * 4096;
tree.insert(base, tree.allocate_span(SpanDesc::free(base, 4096, chunk)));
}
let (source_id, parent_id, left_id, right_id, source_high, source_keys) =
find_cross_parent_boundary(&tree);
for key in source_keys.iter().copied() {
assert!(tree.remove(key).is_some());
}
let handle = tree.collector.register();
let guard = handle.pin();
tree.read_node(source_id, &tree.node(source_id), &guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target } if *target == left_id));
});
let left = tree.node(left_id);
assert_eq!(left.high_key.load(Ordering::Acquire), source_high);
assert_eq!(left.right_sibling.load(Ordering::Acquire), right_id);
assert!(!tree.parent_contains(parent_id, source_id, &guard));
drop(guard);
let reinserted = source_keys[source_keys.len() / 2];
tree.insert(
reinserted,
tree.allocate_span(SpanDesc::free(reinserted, 4096, chunk)),
);
assert_eq!(tree.get(reinserted).unwrap().base, reinserted);
let handle = tree.collector.register();
let guard = handle.pin();
let left_has_reinserted =
tree.read_node(left_id, &tree.node(left_id), &guard, |high, data| {
assert_eq!(high, source_high);
matches!(data, NodeData::Leaf { entries } if entries.iter().any(|entry| entry.0 == reinserted))
});
let right_has_reinserted =
tree.read_node(right_id, &tree.node(right_id), &guard, |_, data| {
matches!(data, NodeData::Leaf { entries } if entries.iter().any(|entry| entry.0 == reinserted))
});
assert!(left_has_reinserted);
assert!(!right_has_reinserted);
drop(guard);
assert_eq!(tree.operation_stats().cross_parent_redirects, 1);
tree.validate().unwrap();
}
#[test]
fn first_child_leaf_splices_its_global_predecessor_and_retires() {
const KEYS: usize = FANOUT * FANOUT;
let tree = AddressTree::new();
let chunk = 0x10_0000;
for index in 0..KEYS {
let base = chunk + index * 4096;
tree.insert(base, tree.allocate_span(SpanDesc::free(base, 4096, chunk)));
}
let (source_id, parent_id, left_id, right_id, source_keys) =
find_first_child_with_global_predecessor(&tree);
let protection_handle = tree.collector.register();
let protection = protection_handle.pin();
for key in source_keys {
assert!(tree.remove(key).is_some());
}
let source = tree.node_guarded(source_id, &protection);
tree.read_node(source_id, &source, &protection, |_, data| {
assert!(matches!(data, NodeData::Redirect { target } if *target == left_id));
});
let left = tree.node_guarded(left_id, &protection);
assert_eq!(left.right_sibling.load(Ordering::Acquire), right_id);
assert!(!tree.parent_contains(parent_id, source_id, &protection));
tree.validate().unwrap();
let retired_before = tree.operation_stats().retired_nodes;
drop(protection);
for _ in 0..128 {
tree.with_guard(|guard| guard.flush());
let guard = protection_handle.pin();
guard.flush();
drop(guard);
if tree.operation_stats().retired_nodes > retired_before {
break;
}
}
assert!(tree.operation_stats().retired_nodes > retired_before);
}
#[test]
fn reader_at_left_neighbor_helps_paused_cross_parent_redirect() {
const KEYS: usize = FANOUT * FANOUT;
let tree = Arc::new(AddressTree::new());
let chunk = 0x10_0000;
for index in 0..KEYS {
let base = chunk + index * 4096;
tree.insert(base, tree.allocate_span(SpanDesc::free(base, 4096, chunk)));
}
let (source_id, parent_id, left_id, right_id, source_high, source_keys) =
find_cross_parent_boundary(&tree);
let source = tree.node(source_id);
let handle = tree.collector.register();
let guard = handle.pin();
let left_key = tree.read_node(left_id, &tree.node(left_id), &guard, |_, data| match data {
NodeData::Leaf { entries } => entries.last().unwrap().0,
_ => panic!("left boundary neighbor must be a leaf"),
});
{
let _write = source.lock();
assert!(source.publish(
NodeData::Leaf {
entries: Vec::new().into(),
},
&guard,
));
}
let (expected_version, expected_data, expected_high, _) =
tree.read_node_snapshot(source_id, &source, &guard);
assert_eq!(expected_high, source_high);
let kind = tree
.redirect_operation_kind(
source_id,
expected_version,
expected_data,
expected_high,
right_id,
&guard,
)
.expect("cross-parent redirect descriptor must be constructible");
assert!(matches!(kind, OperationKind::LeftRedirect { .. }));
source.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind,
}),
Ordering::Release,
);
let operation = source.operation.load(Ordering::Acquire, &guard);
assert!(
source
.version
.compare_exchange(
expected_version,
VERSION_OPERATION_FROZEN | expected_version,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
unsafe { operation.deref() }
.phase
.store(OP_FROZEN, Ordering::Release);
assert!(tree.attach_operation_slot(parent_id, operation, &guard));
assert!(tree.attach_operation_slot(left_id, operation, &guard));
drop(guard);
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(left_key).unwrap().base);
assert_eq!(helper.join().unwrap(), left_key);
assert_eq!(
tree.node(left_id).right_sibling.load(Ordering::Acquire),
right_id
);
assert_eq!(
tree.node(left_id).high_key.load(Ordering::Acquire),
source_high
);
for id in [source_id, parent_id, left_id] {
assert!(
tree.node(id)
.operation
.load(Ordering::Acquire, unsafe { unprotected() })
.is_null()
);
}
let reinserted = source_keys[source_keys.len() / 2];
tree.insert(
reinserted,
tree.allocate_span(SpanDesc::free(reinserted, 4096, chunk)),
);
assert_eq!(tree.get(reinserted).unwrap().base, reinserted);
tree.validate().unwrap();
}
#[test]
fn single_child_internal_node_merges_left_before_leaf_cleanup() {
const KEYS: usize = FANOUT * FANOUT;
let tree = AddressTree::new();
let chunk = 0x10_0000;
for index in 0..KEYS {
let base = chunk + index * 4096;
tree.insert(base, tree.allocate_span(SpanDesc::free(base, 4096, chunk)));
}
let handle = tree.collector.register();
let guard = handle.pin();
let root_id = tree.root.load(Ordering::Acquire);
let root = tree.node(root_id);
let (left_id, source_id) = tree.read_node(root_id, &root, &guard, |_, data| match data {
NodeData::Internal { children, .. } if children.len() >= 3 => {
(children[0], children[1])
}
_ => panic!("test requires a three-level tree with three root children"),
});
let source = tree.node(source_id);
let source_high = source.high_key.load(Ordering::Acquire);
let source_right = source.right_sibling.load(Ordering::Acquire);
let leaf_ids = tree.read_node(source_id, &source, &guard, |_, data| match data {
NodeData::Internal { children, .. } => children.clone(),
_ => panic!("root child must be internal"),
});
let mut removed_keys = Vec::<usize>::new();
for leaf_id in leaf_ids {
let leaf = tree.node(leaf_id);
removed_keys.extend(
tree.read_node(leaf_id, &leaf, &guard, |_, data| match data {
NodeData::Leaf { entries } => {
entries.iter().map(|entry| entry.0).collect::<Vec<_>>()
}
_ => panic!("internal child must be a leaf"),
}),
);
}
drop(guard);
for key in removed_keys.iter().copied() {
assert!(tree.remove(key).is_some(), "missing key {key:#x}");
}
let handle = tree.collector.register();
let guard = handle.pin();
tree.read_node(source_id, &source, &guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target } if *target == left_id));
});
let left = tree.node(left_id);
assert_eq!(left.high_key.load(Ordering::Acquire), source_high);
assert_eq!(left.right_sibling.load(Ordering::Acquire), source_right);
assert!(!tree.parent_contains(root_id, source_id, &guard));
drop(guard);
let reinserted = removed_keys[removed_keys.len() / 2];
tree.insert(
reinserted,
tree.allocate_span(SpanDesc::free(reinserted, 4096, chunk)),
);
assert_eq!(tree.get(reinserted).unwrap().base, reinserted);
assert_eq!(tree.operation_stats().internal_redirects, 1);
tree.validate().unwrap();
}
#[test]
fn first_single_child_internal_node_merges_into_right_sibling() {
const KEYS: usize = FANOUT * FANOUT;
let tree = AddressTree::new();
let chunk = 0x10_0000;
for index in 0..KEYS {
let base = chunk + index * 4096;
tree.insert(base, tree.allocate_span(SpanDesc::free(base, 4096, chunk)));
}
let handle = tree.collector.register();
let guard = handle.pin();
let root_id = tree.root.load(Ordering::Acquire);
let root = tree.node(root_id);
let (source_id, right_id) = tree.read_node(root_id, &root, &guard, |_, data| match data {
NodeData::Internal { children, .. } if children.len() >= 3 => {
(children[0], children[1])
}
_ => panic!("test requires a three-level tree with three root children"),
});
let source = tree.node(source_id);
let leaf_ids = tree.read_node(source_id, &source, &guard, |_, data| match data {
NodeData::Internal { children, .. } => children.clone(),
_ => panic!("root child must be internal"),
});
let mut removed_keys = Vec::<usize>::new();
for leaf_id in leaf_ids {
removed_keys.extend(
tree.read_node(leaf_id, &tree.node(leaf_id), &guard, |_, data| match data {
NodeData::Leaf { entries } => {
entries.iter().map(|entry| entry.0).collect::<Vec<_>>()
}
_ => panic!("internal child must be a leaf"),
}),
);
}
drop(guard);
let retired_before = tree.operation_stats().retired_nodes;
for key in removed_keys.iter().copied() {
assert!(tree.remove(key).is_some(), "missing key {key:#x}");
}
let handle = tree.collector.register();
let guard = handle.pin();
tree.read_node(source_id, &source, &guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target } if *target == right_id));
});
assert!(!tree.parent_contains(root_id, source_id, &guard));
drop(guard);
let reinserted = removed_keys[removed_keys.len() / 2];
tree.insert(
reinserted,
tree.allocate_span(SpanDesc::free(reinserted, 4096, chunk)),
);
assert_eq!(tree.get(reinserted).unwrap().base, reinserted);
assert_eq!(tree.operation_stats().internal_redirects, 1);
tree.validate().unwrap();
for _ in 0..128 {
tree.with_guard(|guard| guard.flush());
let guard = handle.pin();
guard.flush();
drop(guard);
if tree.operation_stats().retired_nodes > retired_before {
break;
}
}
assert!(tree.operation_stats().retired_nodes > retired_before);
}
#[test]
fn cross_parent_internal_predecessor_bypasses_right_redirect_before_retirement() {
let (tree, source_id, left_id, right_id, bases) =
build_cross_parent_right_redirect_fixture();
let retired_before = tree.operation_stats().retired_nodes;
let handle = tree.collector.register();
let guard = handle.pin();
assert_eq!(
tree.find_internal_predecessor(source_id, &guard),
Some(left_id)
);
assert!(tree.try_publish_internal_redirect(source_id, &guard));
let source = tree.node_guarded(source_id, &guard);
tree.read_node(source_id, &source, &guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target } if *target == right_id));
});
assert_eq!(
tree.node_guarded(left_id, &guard)
.right_sibling
.load(Ordering::Acquire),
right_id
);
assert!(tree.find_internal_predecessor(source_id, &guard).is_none());
drop(guard);
for base in bases {
assert_eq!(tree.get(base).unwrap().base, base);
}
tree.validate().unwrap();
for _ in 0..128 {
tree.with_guard(|guard| guard.flush());
let guard = handle.pin();
guard.flush();
drop(guard);
if tree.operation_stats().retired_nodes > retired_before {
break;
}
}
assert!(tree.operation_stats().retired_nodes > retired_before);
}
#[test]
fn reader_helps_right_redirect_paused_before_predecessor_splice() {
let (tree, source_id, left_id, right_id, bases) =
build_cross_parent_right_redirect_fixture();
let tree = Arc::new(tree);
let handle = tree.collector.register();
let guard = handle.pin();
PAUSE_RIGHT_REDIRECT_BEFORE_SPLICE.set(true);
assert!(tree.try_publish_internal_redirect(source_id, &guard));
PAUSE_RIGHT_REDIRECT_BEFORE_SPLICE.set(false);
assert_eq!(
tree.node_guarded(left_id, &guard)
.right_sibling
.load(Ordering::Acquire),
source_id
);
assert!(
!tree
.node_guarded(source_id, &guard)
.operation
.load(Ordering::Acquire, &guard)
.is_null()
);
drop(guard);
let protection = handle.pin();
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || {
helper_tree.with_guard(|guard| {
let source = helper_tree.node_guarded(source_id, guard);
helper_tree.read_node(source_id, &source, guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target } if *target == right_id));
});
});
});
helper.join().unwrap();
assert_eq!(
tree.node_guarded(left_id, &protection)
.right_sibling
.load(Ordering::Acquire),
right_id
);
assert!(
tree.node_guarded(source_id, &protection)
.operation
.load(Ordering::Acquire, &protection)
.is_null()
);
drop(protection);
for base in bases {
assert_eq!(tree.get(base).unwrap().base, base);
}
tree.validate().unwrap();
}
#[test]
fn full_left_internal_sibling_redistributes_with_single_child_source() {
let (tree, source_id, sibling_id, root_id, bases) = build_redistribution_fixture(false);
let handle = tree.collector.register();
let guard = handle.pin();
assert!(tree.try_publish_internal_redirect(source_id, &guard));
let source_children = tree.read_node(
source_id,
&tree.node(source_id),
&guard,
|high, data| match data {
NodeData::Internal { children, .. } => {
assert_eq!(high, usize::MAX);
children.clone()
}
_ => panic!("redistributed source must remain internal"),
},
);
let sibling_children = tree.read_node(
sibling_id,
&tree.node(sibling_id),
&guard,
|high, data| match data {
NodeData::Internal { children, .. } => {
assert_eq!(high, bases[33]);
children.clone()
}
_ => panic!("redistributed sibling must remain internal"),
},
);
assert_eq!(source_children.len(), 33);
assert_eq!(sibling_children.len(), 33);
tree.read_node(root_id, &tree.node(root_id), &guard, |_, data| match data {
NodeData::Internal { keys, children } => {
assert_eq!(keys, &[bases[33]]);
assert_eq!(children, &[sibling_id, source_id]);
}
_ => panic!("redistribution root must remain internal"),
});
drop(guard);
for base in bases {
assert_eq!(tree.get(base).unwrap().base, base);
}
assert_eq!(tree.operation_stats().internal_redistributions, 1);
tree.validate().unwrap();
}
#[test]
fn full_right_internal_sibling_redistributes_with_first_source() {
let (tree, source_id, sibling_id, root_id, bases) = build_redistribution_fixture(true);
let handle = tree.collector.register();
let guard = handle.pin();
assert!(tree.try_publish_internal_redirect(source_id, &guard));
let source_children = tree.read_node(
source_id,
&tree.node(source_id),
&guard,
|high, data| match data {
NodeData::Internal { children, .. } => {
assert_eq!(high, bases[33]);
children.clone()
}
_ => panic!("redistributed source must remain internal"),
},
);
let sibling_children = tree.read_node(
sibling_id,
&tree.node(sibling_id),
&guard,
|high, data| match data {
NodeData::Internal { children, .. } => {
assert_eq!(high, usize::MAX);
children.clone()
}
_ => panic!("redistributed sibling must remain internal"),
},
);
assert_eq!(source_children.len(), 33);
assert_eq!(sibling_children.len(), 33);
tree.read_node(root_id, &tree.node(root_id), &guard, |_, data| match data {
NodeData::Internal { keys, children } => {
assert_eq!(keys, &[bases[33]]);
assert_eq!(children, &[source_id, sibling_id]);
}
_ => panic!("redistribution root must remain internal"),
});
drop(guard);
for base in bases {
assert_eq!(tree.get(base).unwrap().base, base);
}
assert_eq!(tree.operation_stats().internal_redistributions, 1);
tree.validate().unwrap();
}
#[test]
fn reader_helps_redistribution_publisher_paused_after_descriptor_publish() {
let (tree, source_id, _sibling_id, _root_id, bases) = build_redistribution_fixture(false);
let tree = Arc::new(tree);
let handle = tree.collector.register();
let guard = handle.pin();
PAUSE_REDISTRIBUTION_AFTER_PUBLISH.set(true);
let completed = tree.try_publish_internal_redirect(source_id, &guard);
PAUSE_REDISTRIBUTION_AFTER_PUBLISH.set(false);
assert!(!completed);
assert!(
!tree
.node(source_id)
.operation
.load(Ordering::Acquire, &guard)
.is_null()
);
drop(guard);
let source_key = *bases.last().unwrap();
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(source_key).unwrap().base);
assert_eq!(helper.join().unwrap(), source_key);
assert!(
tree.node(source_id)
.operation
.load(Ordering::Acquire, unsafe { unprotected() })
.is_null()
);
for base in bases {
assert_eq!(tree.get(base).unwrap().base, base);
}
tree.validate().unwrap();
}
#[test]
fn reader_helps_a_paused_root_collapse_to_completion() {
let tree = Arc::new(AddressTree::new());
for index in 0..=FANOUT {
let base = 0x10_0000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
let root_id = tree.root.load(Ordering::Acquire);
let root = tree.node(root_id);
let handle = tree.collector.register();
let guard = handle.pin();
let child_id = tree.read_node(root_id, &root, &guard, |_, data| match data {
NodeData::Internal { children, .. } => *children.last().unwrap(),
_ => panic!("split root must be internal"),
});
{
let _write = root.lock();
assert!(root.publish(
NodeData::Internal {
keys: Vec::new().into(),
children: vec![child_id].into(),
},
&guard,
));
}
let (expected_version, expected_data, expected_high, _) =
tree.read_node_snapshot(root_id, &root, &guard);
root.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind: OperationKind::RootCollapse {
expected_version,
expected_data,
child_id,
},
}),
Ordering::Release,
);
drop(guard);
let child_key = 0x10_0000 + FANOUT * 4096;
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(child_key).unwrap().base);
assert_eq!(helper.join().unwrap(), child_key);
assert_eq!(tree.root.load(Ordering::Acquire), child_id);
assert_eq!(tree.node(child_id).parent(), None);
assert!(
root.operation
.load(Ordering::Acquire, unsafe { unprotected() })
.is_null()
);
let handle = tree.collector.register();
let guard = handle.pin();
tree.read_node(root_id, &root, &guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target } if *target == child_id));
});
tree.validate().unwrap();
drop(guard);
for _ in 0..128 {
let guard = handle.pin();
guard.flush();
drop(guard);
if tree.operation_stats().retired_nodes != 0 {
break;
}
}
assert_eq!(tree.operation_stats().retired_nodes, 1);
let reused_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: Vec::new().into(),
},
)));
assert_eq!(reused_id, root_id);
assert_eq!(tree.operation_stats().reused_nodes, 1);
}
#[test]
fn reader_helps_a_paused_redirect_to_completion() {
let tree = Arc::new(AddressTree::new());
for index in 0..=FANOUT {
let base = 0x10_0000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
let leaf_id = 0;
let leaf = tree.node(leaf_id);
let target = leaf.right_sibling.load(Ordering::Acquire);
assert_ne!(target, NO_NODE);
let handle = tree.collector.register();
let guard = handle.pin();
{
let _write = leaf.lock();
assert!(leaf.publish(
NodeData::Leaf {
entries: Vec::new().into(),
},
&guard,
));
}
let (expected_version, expected_data, expected_high, _) =
tree.read_node_snapshot(leaf_id, &leaf, &guard);
leaf.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: expected_high,
kind: OperationKind::Redirect {
expected_version,
expected_data,
target,
},
}),
Ordering::Release,
);
drop(guard);
let redirected_key = 0x10_0000;
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(redirected_key).is_none());
assert!(helper.join().unwrap());
assert!(
leaf.operation
.load(Ordering::Acquire, unsafe { unprotected() })
.is_null()
);
let handle = tree.collector.register();
let guard = handle.pin();
tree.read_node(leaf_id, &leaf, &guard, |_, data| {
assert!(matches!(data, NodeData::Redirect { target: actual } if *actual == target));
});
assert_eq!(tree.root.load(Ordering::Acquire), target);
assert_eq!(tree.node(target).parent(), None);
tree.validate().unwrap();
}
#[test]
fn stale_leaf_hint_cannot_publish_an_out_of_fence_split() {
let tree = AddressTree::new();
for index in 0..=FANOUT {
let base = 0x10_0000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
let stale_leaf_id = 0;
let stale_leaf = tree.node(stale_leaf_id);
let handle = tree.collector.register();
let guard = handle.pin();
let (version, expected_data, high_key, snapshot) =
tree.read_node_snapshot(stale_leaf_id, &stale_leaf, &guard);
assert_ne!(high_key, usize::MAX);
assert_ne!(stale_leaf.right_sibling.load(Ordering::Acquire), NO_NODE);
let out_of_fence = high_key;
assert!(!tree.try_publish_leaf_split(
stale_leaf_id,
version,
expected_data,
high_key,
snapshot,
out_of_fence,
tree.allocate_span(SpanDesc::free(out_of_fence, 4096, 0x10_0000)),
&guard,
));
assert!(
stale_leaf
.operation
.load(Ordering::Acquire, &guard)
.is_null()
);
tree.validate().unwrap();
}
#[test]
fn reader_helps_a_paused_parent_insert_to_completion() {
let tree = Arc::new(AddressTree::new());
let left_id = 0;
let left = tree.node(left_id);
let middle_base = 0x20_0000;
let right_base = 0x30_0000;
let handle = tree.collector.register();
let guard = handle.pin();
{
let _write = left.lock();
left.publish(
NodeData::Leaf {
entries: vec![(
0x10_0000,
tree.allocate_span(SpanDesc::free(0x10_0000, 4096, 0x10_0000)),
)]
.into(),
},
&guard,
);
}
let middle_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: vec![(
middle_base,
tree.allocate_span(SpanDesc::free(middle_base, 4096, 0x10_0000)),
)]
.into(),
},
)));
let right_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Leaf {
entries: vec![(
right_base,
tree.allocate_span(SpanDesc::free(right_base, 4096, 0x10_0000)),
)]
.into(),
},
)));
let root_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: vec![middle_base].into(),
children: vec![left_id, middle_id].into(),
},
)));
tree.root.store(root_id, Ordering::Release);
left.set_parent(Some(root_id));
tree.node(middle_id).set_parent(Some(root_id));
let root = tree.node(root_id);
let expected_data = root.data.load(Ordering::Acquire, &guard).as_raw() as usize;
root.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: usize::MAX,
kind: OperationKind::ParentInsert {
expected_version: root.version.load(Ordering::Acquire),
expected_data,
right_id,
new_data: NodeData::Internal {
keys: vec![middle_base, right_base].into(),
children: vec![left_id, middle_id, right_id].into(),
},
},
}),
Ordering::Release,
);
drop(guard);
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(right_base).unwrap().base);
assert_eq!(helper.join().unwrap(), right_base);
assert_eq!(tree.node(right_id).parent(), Some(root_id));
tree.validate().unwrap();
}
#[test]
fn reader_helps_a_paused_internal_split_to_completion() {
const CHILDREN: usize = FANOUT + 2;
let tree = Arc::new(AddressTree::new());
let handle = tree.collector.register();
let guard = handle.pin();
let mut child_ids = Vec::with_capacity(CHILDREN);
let mut bases = Vec::with_capacity(CHILDREN);
for index in 0..CHILDREN {
let base = 0x10_0000 + index * 4096;
bases.push(base);
let data = NodeData::Leaf {
entries: vec![(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
)]
.into(),
};
let child_id = if index == 0 {
let leaf = tree.node(0);
let _write = leaf.lock();
leaf.publish(data, &guard);
0
} else {
tree.append_node(Arc::new(TreeNode::new(None, None, usize::MAX, data)))
};
child_ids.push(child_id);
}
let root_id = tree.append_node(Arc::new(TreeNode::new(
None,
None,
usize::MAX,
NodeData::Internal {
keys: bases[1..FANOUT + 1].to_vec().into(),
children: child_ids[..FANOUT + 1].to_vec().into(),
},
)));
tree.root.store(root_id, Ordering::Release);
for child in child_ids.iter().take(FANOUT + 1).copied() {
tree.node(child).set_parent(Some(root_id));
}
let root = tree.node(root_id);
let expected_version = root.version.load(Ordering::Acquire);
let expected_data = root.data.load(Ordering::Acquire, &guard).as_raw() as usize;
let mut keys = bases[1..].to_vec();
let mut children = child_ids.clone();
let middle = keys.len() / 2;
let right_keys = keys.split_off(middle + 1);
let separator = keys.pop().unwrap();
let right_children = children.split_off(middle + 1);
root.operation.store(
Owned::new(OperationDescriptor {
phase: AtomicU8::new(OP_INIT),
payload_replaced: AtomicU8::new(0),
replacement_data: AtomicUsize::new(0),
replacement_high: separator,
kind: OperationKind::InternalSplit {
expected_version,
expected_data,
old_right: NO_NODE,
old_high: usize::MAX,
separator,
right_id: AtomicUsize::new(NO_NODE),
root_id: AtomicUsize::new(NO_NODE),
needs_root: true,
left_data: NodeData::Internal {
keys: keys.into(),
children: children.into(),
},
right_data: NodeData::Internal {
keys: right_keys.into(),
children: right_children.clone().into(),
},
moved_children: right_children.into_boxed_slice(),
},
}),
Ordering::Release,
);
drop(guard);
let target = *bases.last().unwrap();
let helper_tree = Arc::clone(&tree);
let helper = thread::spawn(move || helper_tree.get(target).unwrap().base);
assert_eq!(helper.join().unwrap(), target);
assert_ne!(tree.root.load(Ordering::Acquire), root_id);
tree.validate().unwrap();
}
#[test]
fn free_fit_prefers_the_hint_chunk_then_nearest_address() {
let topology = Topology::new();
for (base, chunk) in [
(0x10_0000, 0x10_0000),
(0x20_0000, 0x20_0000),
(0x22_0000, 0x20_0000),
] {
topology.tree.insert(
base,
topology
.tree
.allocate_span(SpanDesc::free(base, 0x1_0000, chunk)),
);
}
let (span, address) = topology
.find_free_fit_near(
4096,
4096,
Some(LocalityHint {
address: 0x21_f000,
chunk_base: 0x20_0000,
}),
Some(7),
)
.unwrap();
assert_eq!(span.base, 0x22_0000);
assert_eq!(address, 0x22_0000);
topology
.tree
.get(0x10_0000)
.unwrap()
.owner
.store(9, std::sync::atomic::Ordering::Release);
topology
.tree
.get(0x22_0000)
.unwrap()
.owner
.store(7, std::sync::atomic::Ordering::Release);
let (owned, _) = topology
.find_free_fit_near(4096, 4096, None, Some(7))
.unwrap();
assert_eq!(owned.base, 0x22_0000);
}
#[test]
fn read_snapshot_groups_small_spans_by_class_in_address_order() {
let topology = Topology::new();
for (base, class_index) in [(0x30_0000, 6), (0x10_0000, 6), (0x20_0000, 3)] {
topology.tree.insert(
base,
topology.tree.allocate_span(SpanDesc::small(
base,
0x10_0000,
class_index,
SIZE_CLASSES[class_index],
)),
);
}
let snapshot = TopologyReadSnapshot::from_topology(&topology);
let bases: Vec<_> = snapshot
.class_spans(6)
.iter()
.map(|span| span.base)
.collect();
assert_eq!(bases, vec![0x10_0000, 0x30_0000]);
}
#[test]
fn deletion_preserves_stale_but_safe_separator_keys() {
let tree = AddressTree::new();
for index in 0..150 {
let base = index * 4096;
tree.insert(base, tree.allocate_span(SpanDesc::free(base, 4096, 0)));
}
for index in (0..150).step_by(3) {
assert!(tree.remove(index * 4096).is_some());
tree.validate().unwrap();
}
for index in 0..150 {
assert_eq!(tree.get(index * 4096).is_some(), index % 3 != 0);
}
}
#[test]
fn concurrent_node_level_inserts_and_removes_preserve_the_right_chain() {
const THREADS: usize = 8;
const PER_THREAD: usize = 512;
let tree = Arc::new(AddressTree::new());
let barrier = Arc::new(Barrier::new(THREADS));
let mut workers = Vec::new();
for thread_index in 0..THREADS {
let tree = Arc::clone(&tree);
let barrier = Arc::clone(&barrier);
workers.push(thread::spawn(move || {
barrier.wait();
for offset in 0..PER_THREAD {
let index = if thread_index % 2 == 0 {
thread_index * PER_THREAD + offset
} else {
thread_index * PER_THREAD + (PER_THREAD - 1 - offset)
};
let base = 0x10_0000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
}));
}
for worker in workers {
worker.join().unwrap();
}
tree.validate().unwrap();
let values = tree.values();
if values.len() != THREADS * PER_THREAD {
let missing = (0..THREADS * PER_THREAD)
.filter(|index| tree.get(0x10_0000 + index * 4096).is_none())
.collect::<Vec<_>>();
panic!(
"tree has {} values instead of {}; missing keys: {missing:?}",
values.len(),
THREADS * PER_THREAD
);
}
let barrier = Arc::new(Barrier::new(THREADS));
let mut workers = Vec::new();
for thread_index in 0..THREADS {
let tree = Arc::clone(&tree);
let barrier = Arc::clone(&barrier);
workers.push(thread::spawn(move || {
barrier.wait();
for offset in (0..PER_THREAD).step_by(3) {
let index = thread_index * PER_THREAD + offset;
assert!(tree.remove(0x10_0000 + index * 4096).is_some());
}
}));
}
for worker in workers {
worker.join().unwrap();
}
tree.validate().unwrap();
for index in 0..THREADS * PER_THREAD {
let removed = index % PER_THREAD % 3 == 0;
assert_eq!(tree.get(0x10_0000 + index * 4096).is_none(), removed);
}
}
#[test]
fn concurrent_empty_leaf_redirect_chains_support_reinsertion() {
const THREADS: usize = 8;
const KEYS: usize = 4096;
let tree = Arc::new(AddressTree::new());
for index in 0..KEYS {
let base = 0x10_0000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
let barrier = Arc::new(Barrier::new(THREADS));
let mut removers = Vec::new();
for thread_index in 0..THREADS {
let tree = Arc::clone(&tree);
let barrier = Arc::clone(&barrier);
removers.push(thread::spawn(move || {
barrier.wait();
for index in (thread_index..KEYS).step_by(THREADS) {
assert!(tree.remove(0x10_0000 + index * 4096).is_some());
}
}));
}
for remover in removers {
remover.join().unwrap();
}
assert!(tree.values().is_empty());
let operation_stats = tree.operation_stats();
assert!(operation_stats.redirects > 0);
tree.validate().unwrap();
let barrier = Arc::new(Barrier::new(THREADS));
let mut inserters = Vec::new();
for thread_index in 0..THREADS {
let tree = Arc::clone(&tree);
let barrier = Arc::clone(&barrier);
inserters.push(thread::spawn(move || {
barrier.wait();
for index in (thread_index..KEYS).step_by(THREADS) {
let base = 0x10_0000 + index * 4096;
tree.insert(
base,
tree.allocate_span(SpanDesc::free(base, 4096, 0x10_0000)),
);
}
}));
}
for inserter in inserters {
inserter.join().unwrap();
}
tree.validate().unwrap();
let values = tree.values();
if values.len() != KEYS {
let missing = (0..KEYS)
.filter(|index| tree.get(0x10_0000 + index * 4096).is_none())
.collect::<Vec<_>>();
panic!(
"redirect reinsertion has {} leaf-chain values instead of {KEYS}; missing={} first={:?}",
values.len(),
missing.len(),
missing.iter().take(32).collect::<Vec<_>>(),
);
}
for index in 0..KEYS {
let base = 0x10_0000 + index * 4096;
assert_eq!(tree.get(base).unwrap().base, base);
}
}
#[test]
fn concurrent_metadata_scan_skips_reserved_but_unpublished_node_slots() {
let tree = Arc::new(AddressTree::new());
let done = Arc::new(AtomicBool::new(false));
let writer_tree = Arc::clone(&tree);
let writer_done = Arc::clone(&done);
let writer = thread::spawn(move || {
for index in 0..4096 {
let base = 0x20_0000 + index * 4096;
writer_tree.insert(
base,
writer_tree.allocate_span(SpanDesc::free(base, 4096, 0x20_0000)),
);
}
writer_done.store(true, Ordering::Release);
});
while !done.load(Ordering::Acquire) {
assert!(tree.metadata_bytes() >= size_of::<AddressTree>());
let values = tree.values();
assert!(values.windows(2).all(|pair| pair[0].base < pair[1].base));
}
writer.join().unwrap();
tree.validate().unwrap();
}
}