use std::collections::TryReserveError;
use std::fmt;
use std::mem::MaybeUninit;
use std::num::NonZeroUsize;
use std::ptr::NonNull;
use super::geometry::PoolGeometry;
use super::virtual_memory::{VirtualMemoryError, VirtualRange};
use super::{invariant_violation, CarrierCount};
use crate::runtime::sync::sync::atomic::{AtomicU64, AtomicU8, Ordering};
use crate::runtime::sync::sync::{Arc, Mutex};
#[cfg(test)]
use {super::virtual_memory::VirtualMemoryOperation, std::ops::Range};
#[derive(Debug)]
pub(super) enum BlockError {
VirtualMemory(VirtualMemoryError),
Allocation(TryReserveError),
AlreadyPrepared,
PreparedCapacityOverflow,
InvalidClaimCount,
ClaimExceedsBlock {
requested: usize,
capacity: usize,
},
}
impl fmt::Display for BlockError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::VirtualMemory(error) => error.fmt(f),
Self::Allocation(error) => write!(f, "block metadata allocation failed: {error}"),
Self::AlreadyPrepared => f.write_str("block already has a prepared incarnation"),
Self::PreparedCapacityOverflow => f.write_str("prepared carrier count would overflow"),
Self::InvalidClaimCount => f.write_str("a carrier claim must be nonzero"),
Self::ClaimExceedsBlock {
requested,
capacity,
} => write!(
f,
"carrier claim {requested} exceeds block capacity {capacity}"
),
}
}
}
impl std::error::Error for BlockError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::VirtualMemory(error) => Some(error),
Self::Allocation(error) => Some(error),
Self::AlreadyPrepared
| Self::PreparedCapacityOverflow
| Self::InvalidClaimCount
| Self::ClaimExceedsBlock { .. } => None,
}
}
}
impl From<VirtualMemoryError> for BlockError {
fn from(error: VirtualMemoryError) -> Self {
Self::VirtualMemory(error)
}
}
impl From<TryReserveError> for BlockError {
fn from(error: TryReserveError) -> Self {
Self::Allocation(error)
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) enum TrimBlocked {
NotPrepared,
FloorViolation,
Busy,
CleanupPending,
}
#[derive(Debug)]
pub(super) enum CleanupRetry {
DeactivationPending(VirtualMemoryError),
ReclaimPending(VirtualMemoryError),
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum MappingState {
Reserved {
reclaim_pending: bool,
},
Prepared,
ActivationRecoveryPending,
DeactivationRecoveryPending,
}
#[repr(u8)]
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum IncarnationState {
Active = 0,
Draining = 1,
Dead = 2,
}
struct AtomicIncarnationState(AtomicU8);
impl AtomicIncarnationState {
fn new(value: IncarnationState) -> Self {
Self(AtomicU8::new(value as u8))
}
fn load(&self, order: Ordering) -> IncarnationState {
Self::decode(self.0.load(order))
}
fn try_start_trim(&self) -> Result<(), IncarnationState> {
self.0
.compare_exchange(
IncarnationState::Active as u8,
IncarnationState::Draining as u8,
Ordering::SeqCst,
Ordering::SeqCst,
)
.map(|_| ())
.map_err(Self::decode)
}
fn restore_active(&self) {
if self
.0
.compare_exchange(
IncarnationState::Draining as u8,
IncarnationState::Active as u8,
Ordering::SeqCst,
Ordering::SeqCst,
)
.is_err()
{
invariant_violation("only a draining incarnation may return to active");
}
}
fn retire(&self) {
if self
.0
.compare_exchange(
IncarnationState::Draining as u8,
IncarnationState::Dead as u8,
Ordering::Release,
Ordering::Acquire,
)
.is_err()
{
invariant_violation("only a draining incarnation may retire");
}
}
fn decode(value: u8) -> IncarnationState {
match value {
value if value == IncarnationState::Active as u8 => IncarnationState::Active,
value if value == IncarnationState::Draining as u8 => IncarnationState::Draining,
value if value == IncarnationState::Dead as u8 => IncarnationState::Dead,
_ => invariant_violation("incarnation contains an invalid state"),
}
}
}
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct CarrierId {
slot: u32,
index: u32,
incarnation: IncarnationIdentity,
}
#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub(super) struct CarrierLocation {
slot_id: u32,
carrier_index: u32,
}
impl CarrierLocation {
pub(super) const fn new(slot_id: u32, carrier_index: u32) -> Self {
Self {
slot_id,
carrier_index,
}
}
pub(super) const fn slot_id(self) -> u32 {
self.slot_id
}
pub(super) const fn carrier_index(self) -> u32 {
self.carrier_index
}
}
#[repr(transparent)]
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct IncarnationIdentity(NonZeroUsize);
#[derive(Clone, Copy, Debug)]
struct WonWord {
word_index: usize,
mask: u64,
}
struct BlockIncarnation {
state: AtomicIncarnationState,
in_use: Box<[AtomicU64]>,
}
impl BlockIncarnation {
fn try_new(bitmap_words: usize) -> Result<Self, TryReserveError> {
let mut in_use = Vec::new();
in_use.try_reserve_exact(bitmap_words)?;
in_use.extend((0..bitmap_words).map(|_| AtomicU64::new(0)));
Ok(Self {
state: AtomicIncarnationState::new(IncarnationState::Active),
in_use: in_use.into_boxed_slice(),
})
}
fn try_new_preclaimed(
geometry: PoolGeometry,
count: CarrierCount,
) -> Result<(Self, Vec<WonWord>), TryReserveError> {
let incarnation = Self::try_new(geometry.bitmap_words())?;
let mut won = Vec::new();
won.try_reserve_exact(geometry.bitmap_words())?;
let mut remaining = count.get();
for (word_index, word) in incarnation.in_use.iter().enumerate() {
if remaining == 0 {
break;
}
let valid = bitmap_word_mask(geometry, word_index);
let mask = take_lowest(valid, remaining);
let taken = mask.count_ones() as usize;
word.store(mask, Ordering::Relaxed);
won.push(WonWord { word_index, mask });
remaining -= taken;
}
if remaining != 0 {
invariant_violation("preclaim exceeds valid block geometry");
}
Ok((incarnation, won))
}
fn identity(this: &Arc<Self>) -> IncarnationIdentity {
let address = Arc::as_ptr(this).addr();
IncarnationIdentity(
NonZeroUsize::new(address).expect("an allocated incarnation has a nonzero address"),
)
}
}
#[cfg(not(all(test, s3_tm_loom)))]
mod incarnation_cell {
use arc_swap::{ArcSwapOption, Guard};
use super::BlockIncarnation;
use crate::runtime::sync::sync::Arc;
pub(super) struct IncarnationCell {
inner: ArcSwapOption<BlockIncarnation>,
}
impl IncarnationCell {
pub(super) fn new() -> Self {
Self {
inner: ArcSwapOption::empty(),
}
}
pub(super) fn load(&self) -> IncarnationGuard {
IncarnationGuard {
inner: self.inner.load(),
}
}
pub(super) fn swap(
&self,
next: Option<Arc<BlockIncarnation>>,
) -> Option<Arc<BlockIncarnation>> {
self.inner.swap(next)
}
}
pub(super) struct IncarnationGuard {
inner: Guard<Option<Arc<BlockIncarnation>>>,
}
impl IncarnationGuard {
pub(super) fn as_ref(&self) -> Option<&Arc<BlockIncarnation>> {
self.inner.as_ref()
}
}
}
#[cfg(all(test, s3_tm_loom))]
mod incarnation_cell {
use super::BlockIncarnation;
use crate::runtime::sync::sync::{Arc, Mutex};
pub(super) struct IncarnationCell {
inner: Mutex<Option<Arc<BlockIncarnation>>>,
}
impl IncarnationCell {
pub(super) fn new() -> Self {
Self {
inner: Mutex::new(None),
}
}
pub(super) fn load(&self) -> IncarnationGuard {
IncarnationGuard {
inner: self.inner.lock().clone(),
}
}
pub(super) fn swap(
&self,
next: Option<Arc<BlockIncarnation>>,
) -> Option<Arc<BlockIncarnation>> {
std::mem::replace(&mut *self.inner.lock(), next)
}
}
pub(super) struct IncarnationGuard {
inner: Option<Arc<BlockIncarnation>>,
}
impl IncarnationGuard {
pub(super) fn as_ref(&self) -> Option<&Arc<BlockIncarnation>> {
self.inner.as_ref()
}
}
}
use incarnation_cell::{IncarnationCell, IncarnationGuard};
pub(super) struct BlockSlot {
id: u32,
range: VirtualRange,
geometry: PoolGeometry,
mapping: Mutex<MappingState>,
current: IncarnationCell,
#[cfg(test)]
release_batches: AtomicU64,
}
impl BlockSlot {
pub(super) fn new(id: u32, geometry: PoolGeometry) -> Result<Self, BlockError> {
let range = VirtualRange::reserve(
geometry.block_size(),
NonZeroUsize::new(geometry.page_size()).expect("geometry has a nonzero page size"),
)?;
Ok(Self::from_range(id, geometry, range))
}
#[cfg(test)]
pub(super) fn new_guarded(id: u32, geometry: PoolGeometry) -> Result<Self, BlockError> {
let range = VirtualRange::reserve_guarded(
geometry.block_size(),
NonZeroUsize::new(geometry.page_size()).expect("geometry has a nonzero page size"),
)?;
Ok(Self::from_range(id, geometry, range))
}
fn from_range(id: u32, geometry: PoolGeometry, range: VirtualRange) -> Self {
Self {
id,
range,
geometry,
mapping: Mutex::new(MappingState::Reserved {
reclaim_pending: false,
}),
current: IncarnationCell::new(),
#[cfg(test)]
release_batches: AtomicU64::new(0),
}
}
pub(super) fn carrier_count(&self) -> CarrierCount {
self.geometry.carriers_per_block()
}
pub(super) fn id(&self) -> u32 {
self.id
}
pub(super) fn base_address(&self) -> usize {
self.range.base_address()
}
pub(super) fn reserved_len(&self) -> usize {
self.range.len()
}
#[cfg(test)]
pub(super) fn reservation_address_range(&self) -> std::ops::Range<usize> {
self.range.reservation_address_range()
}
pub(super) unsafe fn ptr_for_immutable_range(
&self,
offset: usize,
len: usize,
) -> Option<NonNull<u8>> {
unsafe {
self.range
.ptr_for_range(offset, len)
.map(NonNull::cast::<u8>)
}
}
#[cfg(debug_assertions)]
pub(super) fn debug_assert_immutable_range_live(&self, offset: usize, len: usize) {
let end = offset.checked_add(len);
debug_assert!(
len != 0 && end.is_some_and(|end| end <= self.geometry.block_size()),
"immutable range is outside its block slot"
);
let Some(end) = end.filter(|end| len != 0 && *end <= self.geometry.block_size()) else {
return;
};
let current = self.current.load();
let Some(incarnation) = current.as_ref() else {
debug_assert!(false, "immutable range has no current incarnation");
return;
};
let first = offset / self.geometry.carrier_size();
let last = (end - 1) / self.geometry.carrier_size();
for index in first..=last {
let word_index = index / u64::BITS as usize;
let mask = 1u64 << (index % u64::BITS as usize);
let live = incarnation
.in_use
.get(word_index)
.is_some_and(|word| word.load(Ordering::Acquire) & mask != 0);
debug_assert!(
live,
"immutable range includes a carrier without a live bit"
);
}
}
#[cfg(test)]
pub(super) fn address_range(&self) -> Option<Range<usize>> {
let start = self.base_address();
start.checked_add(self.reserved_len()).map(|end| start..end)
}
pub(super) fn bitmap_words(&self) -> usize {
self.geometry.bitmap_words()
}
pub(super) fn prepare(&self, prepared: &mut CarrierCount) -> Result<(), BlockError> {
let mut mapping = self.mapping.lock();
let current = self.current.load();
let create_fresh = match *mapping {
MappingState::Prepared => {
let Some(incarnation) = current.as_ref() else {
invariant_violation("prepared mapping has no current incarnation");
};
if incarnation.state.load(Ordering::Acquire) == IncarnationState::Dead {
invariant_violation("prepared mapping has a dead current incarnation");
}
return Err(BlockError::AlreadyPrepared);
}
MappingState::Reserved { .. } | MappingState::ActivationRecoveryPending => {
if current.as_ref().is_some() {
invariant_violation("inactive mapping retains a current incarnation");
}
true
}
MappingState::DeactivationRecoveryPending => {
let Some(incarnation) = current.as_ref() else {
invariant_violation("deactivation recovery lost its current incarnation");
};
if incarnation.state.load(Ordering::Acquire) != IncarnationState::Draining {
invariant_violation(
"deactivation recovery retained a non-draining incarnation",
);
}
false
}
};
let next_prepared = prepared
.checked_add(self.carrier_count())
.ok_or(BlockError::PreparedCapacityOverflow)?;
let fresh = if create_fresh {
Some(Arc::new(BlockIncarnation::try_new(
self.geometry.bitmap_words(),
)?))
} else {
None
};
if let Err(error) = self.range.prepare() {
*mapping = if current.as_ref().is_some() {
MappingState::DeactivationRecoveryPending
} else {
MappingState::ActivationRecoveryPending
};
return Err(error.into());
}
*mapping = MappingState::Prepared;
*prepared = next_prepared;
if let Some(incarnation) = current.as_ref() {
incarnation.state.restore_active();
} else if self.current.swap(fresh).is_some() {
invariant_violation("preparation replaced a current incarnation");
}
Ok(())
}
pub(super) fn prepare_and_claim_if_inactive(
slot: &Arc<Self>,
prepared: &mut CarrierCount,
count: CarrierCount,
) -> Result<Option<ProvisionalBits>, BlockError> {
if count == CarrierCount::ZERO {
return Err(BlockError::InvalidClaimCount);
}
if count > slot.carrier_count() {
return Err(BlockError::ClaimExceedsBlock {
requested: count.get(),
capacity: slot.carrier_count().get(),
});
}
let mut mapping = slot.mapping.lock();
let current = slot.current.load();
match *mapping {
MappingState::Prepared => {
let Some(incarnation) = current.as_ref() else {
invariant_violation("prepared mapping has no current incarnation");
};
if incarnation.state.load(Ordering::Acquire) == IncarnationState::Dead {
invariant_violation("prepared mapping has a dead current incarnation");
}
return Ok(None);
}
MappingState::DeactivationRecoveryPending => {
let Some(incarnation) = current.as_ref() else {
invariant_violation("deactivation recovery lost its current incarnation");
};
if incarnation.state.load(Ordering::Acquire) != IncarnationState::Draining {
invariant_violation(
"deactivation recovery retained a non-draining incarnation",
);
}
return Ok(None);
}
MappingState::Reserved { .. } | MappingState::ActivationRecoveryPending => {
if current.as_ref().is_some() {
invariant_violation("inactive mapping retains a current incarnation");
}
}
}
let next_prepared = prepared
.checked_add(slot.carrier_count())
.ok_or(BlockError::PreparedCapacityOverflow)?;
let (fresh, won) = BlockIncarnation::try_new_preclaimed(slot.geometry, count)?;
let fresh = Arc::new(fresh);
let incarnation = BlockIncarnation::identity(&fresh);
if let Err(error) = slot.range.prepare() {
*mapping = MappingState::ActivationRecoveryPending;
return Err(error.into());
}
*mapping = MappingState::Prepared;
*prepared = next_prepared;
if slot.current.swap(Some(fresh)).is_some() {
invariant_violation("preclaimed activation replaced a current incarnation");
}
Ok(Some(ProvisionalBits {
slot: Arc::clone(slot),
incarnation,
won,
}))
}
pub(super) fn start_trim(
slot: &Arc<Self>,
prepared: &mut CarrierCount,
floor: CarrierCount,
) -> Result<TrimCleanup, TrimBlocked> {
let mapping = slot.mapping.lock();
match *mapping {
MappingState::Prepared => {}
MappingState::Reserved { .. } => return Err(TrimBlocked::NotPrepared),
MappingState::ActivationRecoveryPending | MappingState::DeactivationRecoveryPending => {
return Err(TrimBlocked::CleanupPending)
}
}
let current = slot.current.load();
let Some(incarnation) = current.as_ref() else {
invariant_violation("prepared mapping has no current incarnation");
};
match incarnation.state.load(Ordering::Acquire) {
IncarnationState::Active => {}
IncarnationState::Draining => return Err(TrimBlocked::CleanupPending),
IncarnationState::Dead => {
invariant_violation("prepared mapping has a dead current incarnation")
}
}
let Some(next_prepared) = prepared.checked_sub(slot.carrier_count()) else {
invariant_violation("prepared capacity excludes an active block");
};
if next_prepared < floor {
return Err(TrimBlocked::FloorViolation);
}
if incarnation.state.try_start_trim().is_err() {
return Err(TrimBlocked::CleanupPending);
}
loom_seq_cst_fence();
let busy = incarnation
.in_use
.iter()
.enumerate()
.any(|(word_index, word)| {
let valid = bitmap_word_mask(slot.geometry, word_index);
word.load(Ordering::SeqCst) & valid != 0
});
if busy {
incarnation.state.restore_active();
return Err(TrimBlocked::Busy);
}
*prepared = next_prepared;
Ok(TrimCleanup {
slot: Arc::clone(slot),
incarnation: Arc::clone(incarnation),
consumed: false,
})
}
pub(super) fn retry_cleanup(&self) -> Result<bool, CleanupRetry> {
let mut mapping = self.mapping.lock();
match *mapping {
MappingState::Prepared => {
let current = self.current.load();
let Some(incarnation) = current.as_ref() else {
invariant_violation("prepared mapping has no current incarnation");
};
match incarnation.state.load(Ordering::Acquire) {
IncarnationState::Active | IncarnationState::Draining => return Ok(false),
IncarnationState::Dead => {
invariant_violation("prepared mapping has a dead current incarnation")
}
}
}
MappingState::Reserved {
reclaim_pending: false,
} => {
if self.current.load().as_ref().is_some() {
invariant_violation("inactive mapping has a current incarnation");
}
return Ok(false);
}
MappingState::Reserved {
reclaim_pending: true,
} => {
if self.current.load().as_ref().is_some() {
invariant_violation("inactive reclaim has a current incarnation");
}
return match self.range.discard() {
Ok(()) => {
*mapping = MappingState::Reserved {
reclaim_pending: false,
};
Ok(true)
}
Err(error) => Err(CleanupRetry::ReclaimPending(error)),
};
}
MappingState::ActivationRecoveryPending => {
if self.current.load().as_ref().is_some() {
invariant_violation("activation recovery retained a current incarnation");
}
}
MappingState::DeactivationRecoveryPending => {
let current = self.current.load();
let Some(incarnation) = current.as_ref() else {
invariant_violation("deactivation recovery lost its current incarnation");
};
if incarnation.state.load(Ordering::Acquire) != IncarnationState::Draining {
invariant_violation(
"deactivation recovery retained a non-draining incarnation",
);
}
}
}
if let Err(error) = self.range.deactivate() {
return Err(CleanupRetry::DeactivationPending(error));
}
*mapping = MappingState::Reserved {
reclaim_pending: false,
};
self.finish_inactive_cleanup(&mut mapping).map(|()| true)
}
fn finish_inactive_cleanup(&self, mapping: &mut MappingState) -> Result<(), CleanupRetry> {
let reclaim = self.range.discard();
let reclaim_pending = reclaim.is_err();
*mapping = MappingState::Reserved { reclaim_pending };
if let Some(incarnation) = self.current.load().as_ref() {
incarnation.state.retire();
let removed = self
.current
.swap(None)
.unwrap_or_else(|| invariant_violation("cleanup lost its current incarnation"));
if !Arc::ptr_eq(&removed, incarnation) {
invariant_violation("cleanup removed a different incarnation");
}
}
match reclaim {
Ok(()) => Ok(()),
Err(error) => Err(CleanupRetry::ReclaimPending(error)),
}
}
#[cfg(test)]
pub(super) fn try_claim(
slot: &Arc<Self>,
count: CarrierCount,
) -> Result<Option<ProvisionalBits>, BlockError> {
Ok(Self::try_claim_words(slot, 0, slot.bitmap_words(), count)?.into_provisional())
}
pub(super) fn try_claim_exhaustive(
slot: &Arc<Self>,
count: CarrierCount,
) -> Result<Option<ProvisionalBits>, BlockError> {
if count == CarrierCount::ZERO {
return Err(BlockError::InvalidClaimCount);
}
let Some(mut attempt) = BlockClaimAttempt::begin(slot)? else {
return Ok(None);
};
attempt.take_exhaustive(count.get());
Ok(attempt.finish())
}
pub(super) fn try_claim_words(
slot: &Arc<Self>,
start_word: usize,
word_limit: usize,
count: CarrierCount,
) -> Result<BlockClaim, BlockError> {
if count == CarrierCount::ZERO {
return Err(BlockError::InvalidClaimCount);
}
let inspected_words = slot
.bitmap_words()
.saturating_sub(start_word)
.min(word_limit);
if inspected_words == 0 {
return Ok(BlockClaim::empty());
}
let Some(mut attempt) = BlockClaimAttempt::begin_with_capacity(slot, inspected_words)?
else {
return Ok(BlockClaim {
provisional: None,
inspected_words,
});
};
let (_, inspected_words) = attempt.take_words(start_word, inspected_words, count.get());
Ok(BlockClaim {
provisional: attempt.finish(),
inspected_words,
})
}
pub(super) fn try_claim_word_run(
slot: &Arc<Self>,
start_word: usize,
word_limit: usize,
word_count: usize,
) -> Result<BlockClaim, BlockError> {
if word_count == 0 {
return Err(BlockError::InvalidClaimCount);
}
let inspected_limit = slot
.bitmap_words()
.saturating_sub(start_word)
.min(word_limit);
if inspected_limit == 0 {
return Ok(BlockClaim::empty());
}
let Some(mut attempt) = BlockClaimAttempt::begin_with_capacity(slot, word_count)? else {
return Ok(BlockClaim {
provisional: None,
inspected_words: inspected_limit,
});
};
let (complete, inspected_words) =
attempt.take_word_run(start_word, inspected_limit, word_count);
if !complete {
drop(attempt);
return Ok(BlockClaim {
provisional: None,
inspected_words,
});
}
Ok(BlockClaim {
provisional: attempt.finish(),
inspected_words,
})
}
fn release_won(&self, incarnation: IncarnationIdentity, won: &[WonWord]) {
if won.iter().all(|word| word.mask == 0) {
return;
}
#[cfg(test)]
self.release_batches.fetch_add(1, Ordering::AcqRel);
let current = self.current.load();
let Some(current) = current.as_ref() else {
invariant_violation("owned carriers have no current incarnation");
};
if BlockIncarnation::identity(current) != incarnation {
invariant_violation("owned carriers name a different incarnation");
}
match current.state.load(Ordering::Acquire) {
IncarnationState::Active | IncarnationState::Draining => {}
IncarnationState::Dead => invariant_violation("owned carriers name a dead incarnation"),
}
for word in won {
clear_owned_bits(¤t.in_use[word.word_index], word.mask);
}
}
fn release_one(&self, id: CarrierId) {
if id.slot != self.id {
invariant_violation("carrier returned to a different block slot");
}
let index = id.index as usize;
self.release_won(
id.incarnation,
&[WonWord {
word_index: index / u64::BITS as usize,
mask: 1u64 << (index % u64::BITS as usize),
}],
);
}
#[cfg(test)]
pub(super) fn test_release_batches(&self) -> u64 {
self.release_batches.load(Ordering::Acquire)
}
pub(super) fn appears_free(&self) -> bool {
let current = self.current.load();
let Some(incarnation) = current.as_ref() else {
return false;
};
if incarnation.state.load(Ordering::Acquire) != IncarnationState::Active {
return false;
}
incarnation
.in_use
.iter()
.enumerate()
.all(|(word_index, word)| {
let valid = bitmap_word_mask(self.geometry, word_index);
word.load(Ordering::Acquire) & valid == 0
})
}
#[cfg(any(test, s3_tm_fuzz))]
pub(super) fn has_free_word_run_quiescent(&self, word_count: usize) -> bool {
if word_count == 0 {
return false;
}
let current = self.current.load();
let Some(incarnation) = current.as_ref() else {
return false;
};
if incarnation.state.load(Ordering::Acquire) != IncarnationState::Active {
return false;
}
let mut free_words = 0;
for (word_index, word) in incarnation.in_use.iter().enumerate() {
let valid = bitmap_word_mask(self.geometry, word_index);
if valid == u64::MAX && word.load(Ordering::Acquire) & valid == 0 {
free_words += 1;
if free_words == word_count {
return true;
}
} else {
free_words = 0;
}
}
false
}
#[cfg(test)]
pub(super) fn live_carriers(&self) -> usize {
self.current
.load()
.as_ref()
.map(|incarnation| {
incarnation
.in_use
.iter()
.enumerate()
.map(|(word_index, word)| {
let valid = bitmap_word_mask(self.geometry, word_index);
(word.load(Ordering::Acquire) & valid).count_ones() as usize
})
.sum()
})
.unwrap_or(0)
}
#[cfg(test)]
pub(super) fn inject_failure_once(&self, operation: VirtualMemoryOperation) {
self.range.inject_failure_once(operation);
}
pub(super) fn sample_lifecycle(&self) -> BlockLifecycleSample {
let mapping = self.mapping.lock();
let current = self.current.load();
let live_carriers = current
.as_ref()
.map(|incarnation| {
incarnation
.in_use
.iter()
.enumerate()
.map(|(word_index, word)| {
let valid = bitmap_word_mask(self.geometry, word_index);
CarrierCount::new(
(word.load(Ordering::Acquire) & valid).count_ones() as usize
)
})
.fold(CarrierCount::ZERO, |total, count| {
total.checked_add(count).unwrap_or_else(|| {
invariant_violation("block live-carrier diagnostic overflow")
})
})
})
.unwrap_or(CarrierCount::ZERO);
let (prepared_capacity, cleanup_pending) = match *mapping {
MappingState::Prepared => {
let Some(incarnation) = current.as_ref() else {
invariant_violation("prepared mapping has no current incarnation");
};
match incarnation.state.load(Ordering::Acquire) {
IncarnationState::Active => (self.carrier_count(), false),
IncarnationState::Draining => (CarrierCount::ZERO, true),
IncarnationState::Dead => {
invariant_violation("prepared mapping has a dead incarnation")
}
}
}
MappingState::Reserved { reclaim_pending } => {
if current.as_ref().is_some() {
invariant_violation("reserved mapping retains a current incarnation");
}
(CarrierCount::ZERO, reclaim_pending)
}
MappingState::ActivationRecoveryPending => {
if current.as_ref().is_some() {
invariant_violation("activation recovery retains a current incarnation");
}
(CarrierCount::ZERO, true)
}
MappingState::DeactivationRecoveryPending => {
let Some(incarnation) = current.as_ref() else {
invariant_violation("deactivation recovery lost its current incarnation");
};
if incarnation.state.load(Ordering::Acquire) != IncarnationState::Draining {
invariant_violation("deactivation recovery has a non-draining incarnation");
}
(CarrierCount::ZERO, true)
}
};
BlockLifecycleSample {
prepared_capacity,
live_carriers,
cleanup_pending,
}
}
}
pub(super) struct BlockLifecycleSample {
pub(super) prepared_capacity: CarrierCount,
pub(super) live_carriers: CarrierCount,
pub(super) cleanup_pending: bool,
}
pub(super) struct BlockClaim {
provisional: Option<ProvisionalBits>,
inspected_words: usize,
}
impl BlockClaim {
fn empty() -> Self {
Self {
provisional: None,
inspected_words: 0,
}
}
pub(super) fn inspected_words(&self) -> usize {
self.inspected_words
}
pub(super) fn into_provisional(self) -> Option<ProvisionalBits> {
self.provisional
}
}
#[must_use = "confirmed trim cleanup must be completed or dropped"]
pub(super) struct TrimCleanup {
slot: Arc<BlockSlot>,
incarnation: Arc<BlockIncarnation>,
consumed: bool,
}
impl TrimCleanup {
pub(super) fn carrier_count(&self) -> CarrierCount {
self.slot.carrier_count()
}
pub(super) fn finish(mut self) -> Result<(), CleanupRetry> {
self.consumed = true;
self.finish_inner()
}
fn finish_inner(&self) -> Result<(), CleanupRetry> {
let mut mapping = self.slot.mapping.lock();
if !matches!(*mapping, MappingState::Prepared) {
invariant_violation("trim cleanup started from a non-prepared mapping");
}
let current = self.slot.current.load();
let Some(incarnation) = current.as_ref() else {
invariant_violation("trim cleanup lost its current incarnation");
};
if !Arc::ptr_eq(incarnation, &self.incarnation)
|| incarnation.state.load(Ordering::Acquire) != IncarnationState::Draining
{
invariant_violation("trim cleanup no longer owns the draining incarnation");
}
if let Err(error) = self.slot.range.deactivate() {
*mapping = MappingState::DeactivationRecoveryPending;
return Err(CleanupRetry::DeactivationPending(error));
}
*mapping = MappingState::Reserved {
reclaim_pending: false,
};
self.slot.finish_inactive_cleanup(&mut mapping)
}
}
impl Drop for TrimCleanup {
fn drop(&mut self) {
if !self.consumed {
self.consumed = true;
let _ = self.finish_inner();
}
}
}
struct BlockClaimAttempt {
slot: Arc<BlockSlot>,
incarnation: IncarnationGuard,
won: Vec<WonWord>,
}
impl BlockClaimAttempt {
fn begin(slot: &Arc<BlockSlot>) -> Result<Option<Self>, TryReserveError> {
Self::begin_with_capacity(slot, slot.geometry.bitmap_words())
}
fn begin_with_capacity(
slot: &Arc<BlockSlot>,
won_capacity: usize,
) -> Result<Option<Self>, TryReserveError> {
let incarnation = slot.current.load();
if incarnation.as_ref().is_none() {
return Ok(None);
}
let mut won = Vec::new();
won.try_reserve_exact(won_capacity)?;
Ok(Some(Self {
slot: Arc::clone(slot),
incarnation,
won,
}))
}
#[cfg(test)]
fn take(&mut self, count: usize) -> usize {
self.take_words(0, self.slot.geometry.bitmap_words(), count)
.0
}
fn take_words(
&mut self,
start_word: usize,
word_count: usize,
mut count: usize,
) -> (usize, usize) {
let incarnation = self
.incarnation
.as_ref()
.expect("a claim attempt protects one incarnation");
let mut taken = 0;
let mut inspected = 0;
let end_word = start_word
.saturating_add(word_count)
.min(incarnation.in_use.len());
let start_word = start_word.min(end_word);
for word_index in start_word..end_word {
if count == 0 {
break;
}
inspected += 1;
let word = &incarnation.in_use[word_index];
let valid = bitmap_word_mask(self.slot.geometry, word_index);
let observed = word.load(Ordering::Relaxed);
let candidate = take_lowest(!observed & valid, count);
if candidate == 0 {
continue;
}
let previous = word.fetch_or(candidate, Ordering::SeqCst);
let won = candidate & !previous;
if won != 0 {
let won_count = won.count_ones() as usize;
record_won(&mut self.won, word_index, won);
count -= won_count;
taken += won_count;
}
}
(taken, inspected)
}
fn take_word_run(
&mut self,
start_word: usize,
word_limit: usize,
word_count: usize,
) -> (bool, usize) {
let incarnation = self
.incarnation
.as_ref()
.expect("a claim attempt protects one incarnation");
let end_word = start_word
.saturating_add(word_limit)
.min(incarnation.in_use.len());
let scan_start = start_word.min(end_word);
let mut run_start = scan_start;
let mut inspected = 0;
for word_index in scan_start..end_word {
inspected += 1;
let fully_free = bitmap_word_mask(self.slot.geometry, word_index) == u64::MAX
&& incarnation.in_use[word_index].load(Ordering::Relaxed) == 0;
if !fully_free {
run_start = word_index + 1;
continue;
}
if word_index + 1 - run_start < word_count {
continue;
}
for index in run_start..=word_index {
if incarnation.in_use[index]
.compare_exchange(0, u64::MAX, Ordering::SeqCst, Ordering::Relaxed)
.is_err()
{
return (false, inspected);
}
record_won(&mut self.won, index, u64::MAX);
}
return (true, inspected);
}
(false, inspected)
}
fn take_exhaustive(&mut self, mut count: usize) -> usize {
let incarnation = self
.incarnation
.as_ref()
.expect("a claim attempt protects one incarnation");
let mut taken = 0;
for (word_index, word) in incarnation.in_use.iter().enumerate() {
let mut observed = word.load(Ordering::Relaxed);
while count != 0 {
let valid = bitmap_word_mask(self.slot.geometry, word_index);
let candidate = take_lowest(!observed & valid, count);
if candidate == 0 {
break;
}
let previous = word.fetch_or(candidate, Ordering::SeqCst);
observed = previous | candidate;
let won = candidate & !previous;
if won != 0 {
let won_count = won.count_ones() as usize;
record_won(&mut self.won, word_index, won);
count -= won_count;
taken += won_count;
}
}
if count == 0 {
break;
}
}
taken
}
fn finish(mut self) -> Option<ProvisionalBits> {
if self.won.is_empty() {
return None;
}
let incarnation = self
.incarnation
.as_ref()
.expect("a claim attempt protects one incarnation");
loom_seq_cst_fence();
match incarnation.state.load(Ordering::SeqCst) {
IncarnationState::Active => {}
IncarnationState::Draining | IncarnationState::Dead => {
self.rollback_original();
return None;
}
}
let incarnation = BlockIncarnation::identity(incarnation);
let won = std::mem::take(&mut self.won);
Some(ProvisionalBits {
slot: Arc::clone(&self.slot),
incarnation,
won,
})
}
fn rollback_original(&mut self) {
let Some(incarnation) = self.incarnation.as_ref() else {
return;
};
for word in self.won.drain(..) {
clear_owned_bits(&incarnation.in_use[word.word_index], word.mask);
}
}
}
impl Drop for BlockClaimAttempt {
fn drop(&mut self) {
self.rollback_original();
}
}
pub(super) struct ProvisionalBits {
slot: Arc<BlockSlot>,
incarnation: IncarnationIdentity,
won: Vec<WonWord>,
}
impl ProvisionalBits {
pub(super) fn len(&self) -> CarrierCount {
CarrierCount::new(
self.won
.iter()
.map(|word| word.mask.count_ones() as usize)
.sum(),
)
}
pub(super) fn into_carriers(mut self) -> Result<Vec<CarrierAllocation>, BlockError> {
let mut carriers = Vec::new();
carriers.try_reserve_exact(self.len().get())?;
for word in &mut self.won {
while word.mask != 0 {
let bit = word.mask.trailing_zeros() as usize;
let mask = 1u64 << bit;
let index = word.word_index * u64::BITS as usize + bit;
let index = u32::try_from(index)
.unwrap_or_else(|_| invariant_violation("carrier index exceeds geometry"));
let carrier = CarrierAllocation {
slot: Arc::clone(&self.slot),
id: Some(CarrierId {
slot: self.slot.id,
index,
incarnation: self.incarnation,
}),
};
word.mask &= !mask;
carriers.push(carrier);
}
}
Ok(carriers)
}
}
impl Drop for ProvisionalBits {
fn drop(&mut self) {
self.slot.release_won(self.incarnation, &self.won);
}
}
pub(super) struct CarrierAllocation {
slot: Arc<BlockSlot>,
id: Option<CarrierId>,
}
impl CarrierAllocation {
fn id(&self) -> CarrierId {
self.id
.unwrap_or_else(|| invariant_violation("carrier allocation returned its bit twice"))
}
pub(super) fn slot(&self) -> &Arc<BlockSlot> {
&self.slot
}
pub(super) fn location(&self) -> CarrierLocation {
let id = self.id();
CarrierLocation::new(id.slot, id.index)
}
pub(super) fn slot_id(&self) -> u32 {
self.location().slot_id()
}
pub(super) fn carrier_index(&self) -> u32 {
self.location().carrier_index()
}
pub(super) fn capacity(&self) -> usize {
self.slot.geometry.carrier_size()
}
pub(super) fn ptr(&self) -> NonNull<MaybeUninit<u8>> {
let index = self.id().index as usize;
let offset = self
.slot
.geometry
.carrier_offset(index)
.unwrap_or_else(|| invariant_violation("carrier index is outside block geometry"));
unsafe {
self.slot
.range
.ptr_for_range(offset, self.capacity())
.unwrap_or_else(|| invariant_violation("carrier range is outside its reservation"))
}
}
}
impl Drop for CarrierAllocation {
fn drop(&mut self) {
if let Some(id) = self.id.take() {
self.slot.release_one(id);
}
}
}
struct CarrierWordReturn {
slot: Arc<BlockSlot>,
incarnation: IncarnationIdentity,
word_index: usize,
mask: u64,
}
impl Drop for CarrierWordReturn {
fn drop(&mut self) {
self.slot.release_won(
self.incarnation,
&[WonWord {
word_index: self.word_index,
mask: self.mask,
}],
);
}
}
pub(super) struct CarrierAllocationBatch {
current: Option<CarrierWordReturn>,
}
impl CarrierAllocationBatch {
pub(super) fn new() -> Self {
Self { current: None }
}
pub(super) fn push(&mut self, allocation: &mut CarrierAllocation) {
let id = allocation.id();
let word_index = id.index as usize / u64::BITS as usize;
let mask = 1u64 << (id.index as usize % u64::BITS as usize);
let can_extend = self.current.as_ref().is_some_and(|word| {
Arc::ptr_eq(&word.slot, &allocation.slot)
&& word.incarnation == id.incarnation
&& word.word_index == word_index
});
if can_extend {
self.current
.as_mut()
.unwrap_or_else(|| invariant_violation("carrier return group disappeared"))
.mask |= mask;
} else {
drop(self.current.take());
self.current = Some(CarrierWordReturn {
slot: Arc::clone(&allocation.slot),
incarnation: id.incarnation,
word_index,
mask,
});
}
allocation.id = None;
}
}
fn clear_owned_bits(word: &AtomicU64, mask: u64) {
if mask == 0 {
return;
}
let mut observed = word.load(Ordering::Acquire);
loop {
if observed & mask != mask {
invariant_violation("bitmap release does not own every cleared bit");
}
match word.compare_exchange_weak(
observed,
observed & !mask,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return,
Err(actual) => observed = actual,
}
}
}
fn bitmap_word_mask(geometry: PoolGeometry, word_index: usize) -> u64 {
geometry
.bitmap_word_mask(word_index)
.unwrap_or_else(|| invariant_violation("incarnation bitmap exceeds block geometry"))
}
fn take_lowest(available: u64, count: usize) -> u64 {
let mut remaining = available;
for _ in 0..count.min(u64::BITS as usize) {
if remaining == 0 {
break;
}
remaining &= remaining - 1;
}
available ^ remaining
}
fn record_won(won: &mut Vec<WonWord>, word_index: usize, mask: u64) {
if let Some(word) = won.last_mut().filter(|word| word.word_index == word_index) {
word.mask |= mask;
} else {
won.push(WonWord { word_index, mask });
}
}
#[inline]
fn loom_seq_cst_fence() {
#[cfg(all(test, s3_tm_loom))]
loom::sync::atomic::fence(Ordering::SeqCst);
}
#[cfg(all(test, not(s3_tm_loom)))]
mod tests {
use std::panic::{catch_unwind, AssertUnwindSafe};
use super::super::virtual_memory::{page_size, VirtualMemoryOperation};
use super::*;
fn geometry(carriers: usize) -> PoolGeometry {
let page_size = page_size().unwrap().get();
PoolGeometry::new(page_size, page_size * carriers, page_size).unwrap()
}
fn prepared_slot(carriers: usize) -> (Arc<BlockSlot>, CarrierCount) {
let slot = Arc::new(BlockSlot::new(7, geometry(carriers)).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
(slot, prepared)
}
fn current_identity(slot: &BlockSlot) -> Option<IncarnationIdentity> {
slot.current.load().as_ref().map(BlockIncarnation::identity)
}
fn assert_mapping(slot: &BlockSlot, expected: MappingState) {
assert_eq!(*slot.mapping.lock(), expected);
}
#[test]
fn incarnation_transitions_enforce_their_predecessors() {
let state = AtomicIncarnationState::new(IncarnationState::Active);
assert_eq!(state.try_start_trim(), Ok(()));
assert_eq!(state.load(Ordering::Acquire), IncarnationState::Draining);
assert_eq!(state.try_start_trim(), Err(IncarnationState::Draining));
state.restore_active();
assert_eq!(state.load(Ordering::Acquire), IncarnationState::Active);
let invalid_retire = catch_unwind(AssertUnwindSafe(|| state.retire()));
assert!(invalid_retire.is_err());
assert_eq!(state.load(Ordering::Acquire), IncarnationState::Active);
state.try_start_trim().unwrap();
state.retire();
assert_eq!(state.load(Ordering::Acquire), IncarnationState::Dead);
let invalid_restore = catch_unwind(AssertUnwindSafe(|| state.restore_active()));
assert!(invalid_restore.is_err());
assert_eq!(state.load(Ordering::Acquire), IncarnationState::Dead);
}
#[test]
fn preparation_publishes_claimable_capacity() {
let (slot, prepared) = prepared_slot(3);
assert_eq!(prepared, CarrierCount::new(3));
let claimed = BlockSlot::try_claim(&slot, CarrierCount::new(3))
.unwrap()
.unwrap();
assert_eq!(claimed.len(), CarrierCount::new(3));
assert_eq!(slot.live_carriers(), 3);
drop(claimed);
assert_eq!(slot.live_carriers(), 0);
}
#[cfg(debug_assertions)]
#[test]
fn test_immutable_range_live_check_covers_each_intersecting_carrier() {
let (slot, _) = prepared_slot(3);
let carrier_size = slot.geometry.carrier_size();
let claimed = BlockSlot::try_claim(&slot, CarrierCount::new(2))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
slot.debug_assert_immutable_range_live(carrier_size - 1, 2);
drop(claimed);
let missing_live_bit = catch_unwind(AssertUnwindSafe(|| {
slot.debug_assert_immutable_range_live(carrier_size - 1, 2);
}));
assert!(missing_live_bit.is_err());
}
#[test]
fn preclaimed_activation_publishes_owned_bits() {
let slot = Arc::new(BlockSlot::new(7, geometry(4)).unwrap());
let mut prepared = CarrierCount::ZERO;
let preclaimed =
BlockSlot::prepare_and_claim_if_inactive(&slot, &mut prepared, CarrierCount::new(2))
.unwrap()
.expect("fresh slot should activate");
assert_eq!(prepared, CarrierCount::new(4));
assert_eq!(preclaimed.len(), CarrierCount::new(2));
assert_eq!(slot.live_carriers(), 2);
let preclaimed = preclaimed.into_carriers().unwrap();
assert_eq!(
preclaimed
.iter()
.map(|carrier| carrier.id().index)
.collect::<Vec<_>>(),
vec![0, 1]
);
let remaining = BlockSlot::try_claim(&slot, CarrierCount::new(4))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
assert_eq!(
remaining
.iter()
.map(|carrier| carrier.id().index)
.collect::<Vec<_>>(),
vec![2, 3]
);
drop(preclaimed);
drop(remaining);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn preclaimed_activation_crosses_bitmap_words_without_padding() {
let slot = Arc::new(BlockSlot::new(7, geometry(70)).unwrap());
let mut prepared = CarrierCount::ZERO;
let preclaimed =
BlockSlot::prepare_and_claim_if_inactive(&slot, &mut prepared, CarrierCount::new(67))
.unwrap()
.expect("fresh slot should activate")
.into_carriers()
.unwrap();
assert_eq!(prepared, CarrierCount::new(70));
assert_eq!(preclaimed.len(), 67);
assert_eq!(preclaimed.first().unwrap().carrier_index(), 0);
assert_eq!(preclaimed.last().unwrap().carrier_index(), 66);
let remaining = BlockSlot::try_claim(&slot, CarrierCount::new(70))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
assert_eq!(
remaining
.iter()
.map(CarrierAllocation::carrier_index)
.collect::<Vec<_>>(),
vec![67, 68, 69]
);
assert!(BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.is_none());
drop(preclaimed);
drop(remaining);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn failed_preclaimed_activation_publishes_no_ownership() {
let slot = Arc::new(BlockSlot::new(7, geometry(2)).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.range
.inject_failure_once(VirtualMemoryOperation::Prepare);
let error = match BlockSlot::prepare_and_claim_if_inactive(
&slot,
&mut prepared,
CarrierCount::new(1),
) {
Ok(_) => panic!("injected preparation failure must reject activation"),
Err(error) => error,
};
assert!(matches!(
error,
BlockError::VirtualMemory(ref error)
if error.operation() == VirtualMemoryOperation::Prepare
));
assert_eq!(prepared, CarrierCount::ZERO);
assert_eq!(slot.live_carriers(), 0);
assert!(current_identity(&slot).is_none());
assert_mapping(&slot, MappingState::ActivationRecoveryPending);
}
#[test]
fn preclaimed_activation_rejects_invalid_counts_without_mutation() {
let slot = Arc::new(BlockSlot::new(7, geometry(2)).unwrap());
let mut prepared = CarrierCount::ZERO;
assert!(matches!(
BlockSlot::prepare_and_claim_if_inactive(&slot, &mut prepared, CarrierCount::ZERO),
Err(BlockError::InvalidClaimCount)
));
assert!(matches!(
BlockSlot::prepare_and_claim_if_inactive(&slot, &mut prepared, CarrierCount::new(3)),
Err(BlockError::ClaimExceedsBlock {
requested: 3,
capacity: 2
})
));
assert_eq!(prepared, CarrierCount::ZERO);
assert_eq!(slot.live_carriers(), 0);
assert!(current_identity(&slot).is_none());
assert_mapping(
&slot,
MappingState::Reserved {
reclaim_pending: false,
},
);
}
#[test]
fn preclaimed_activation_does_not_replace_retained_metadata() {
let (slot, mut prepared) = prepared_slot(1);
let identity = current_identity(&slot).unwrap();
slot.range
.inject_failure_once(VirtualMemoryOperation::Deactivate);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
assert!(matches!(
cleanup.finish(),
Err(CleanupRetry::DeactivationPending(_))
));
assert!(BlockSlot::prepare_and_claim_if_inactive(
&slot,
&mut prepared,
CarrierCount::new(1)
)
.unwrap()
.is_none());
assert_eq!(prepared, CarrierCount::ZERO);
assert_eq!(current_identity(&slot), Some(identity));
assert_eq!(slot.live_carriers(), 0);
slot.prepare(&mut prepared).unwrap();
assert_eq!(prepared, CarrierCount::new(1));
assert_eq!(current_identity(&slot), Some(identity));
}
#[test]
fn preparation_rejects_a_current_incarnation() {
let (slot, mut prepared) = prepared_slot(1);
assert!(matches!(
slot.prepare(&mut prepared),
Err(BlockError::AlreadyPrepared)
));
assert_eq!(prepared, CarrierCount::new(1));
}
#[test]
fn failed_prepare_stays_nonclaimable_until_recovery() {
let slot = Arc::new(BlockSlot::new(7, geometry(1)).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.range
.inject_failure_once(VirtualMemoryOperation::Prepare);
let error = slot.prepare(&mut prepared).unwrap_err();
assert!(matches!(
error,
BlockError::VirtualMemory(ref error)
if error.operation() == VirtualMemoryOperation::Prepare
));
assert_eq!(prepared, CarrierCount::ZERO);
assert_mapping(&slot, MappingState::ActivationRecoveryPending);
assert!(current_identity(&slot).is_none());
assert!(BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.is_none());
slot.prepare(&mut prepared).unwrap();
assert_eq!(prepared, CarrierCount::new(1));
assert_mapping(&slot, MappingState::Prepared);
assert!(current_identity(&slot).is_some());
}
#[test]
fn cleanup_retry_restores_reserved_state_after_initial_prepare_failure() {
let slot = Arc::new(BlockSlot::new(7, geometry(1)).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.range
.inject_failure_once(VirtualMemoryOperation::Prepare);
assert!(slot.prepare(&mut prepared).is_err());
assert_mapping(&slot, MappingState::ActivationRecoveryPending);
assert!(current_identity(&slot).is_none());
slot.retry_cleanup().unwrap();
assert_eq!(prepared, CarrierCount::ZERO);
assert_mapping(
&slot,
MappingState::Reserved {
reclaim_pending: false,
},
);
assert!(current_identity(&slot).is_none());
slot.prepare(&mut prepared).unwrap();
assert_eq!(prepared, CarrierCount::new(1));
let carrier = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.expect("cleaned slot is claimable");
drop(carrier);
}
#[test]
fn cleanup_retry_is_a_noop_without_pending_work() {
let slot = Arc::new(BlockSlot::new(7, geometry(1)).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.retry_cleanup().unwrap();
assert!(matches!(
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO),
Err(TrimBlocked::NotPrepared)
));
slot.prepare(&mut prepared).unwrap();
slot.retry_cleanup().unwrap();
assert_eq!(prepared, CarrierCount::new(1));
assert_mapping(&slot, MappingState::Prepared);
}
#[test]
fn carrier_pointer_is_derived_from_live_ownership() {
let (slot, _) = prepared_slot(1);
let mut carriers = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
let carrier = carriers.pop().unwrap();
assert_eq!(carrier.capacity(), geometry(1).carrier_size());
unsafe { carrier.ptr().as_ptr().write(MaybeUninit::new(0x5a)) };
assert_eq!(unsafe { carrier.ptr().as_ptr().read().assume_init() }, 0x5a);
drop(carrier);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn bounded_claim_inspects_only_its_word_window() {
let (slot, _) = prepared_slot(130);
let claim = BlockSlot::try_claim_words(&slot, 1, 1, CarrierCount::new(2)).unwrap();
assert_eq!(claim.inspected_words(), 1);
let carriers = claim.into_provisional().unwrap().into_carriers().unwrap();
assert_eq!(
carriers
.iter()
.map(|carrier| carrier.id().index)
.collect::<Vec<_>>(),
vec![64, 65]
);
drop(carriers);
let final_word =
BlockSlot::try_claim_words(&slot, 2, usize::MAX, CarrierCount::new(8)).unwrap();
assert_eq!(final_word.inspected_words(), 1);
let carriers = final_word
.into_provisional()
.unwrap()
.into_carriers()
.unwrap();
assert_eq!(
carriers
.iter()
.map(|carrier| carrier.id().index)
.collect::<Vec<_>>(),
vec![128, 129]
);
drop(carriers);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn word_run_claim_skips_fragmented_prefix() {
let (slot, _) = prepared_slot(192);
let mut occupied = BlockSlot::try_claim(&slot, CarrierCount::new(192))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
drop(occupied.drain(64..128).collect::<Vec<_>>());
let claim = BlockSlot::try_claim_word_run(&slot, 0, 3, 1).unwrap();
assert_eq!(claim.inspected_words(), 2);
let run = claim.into_provisional().unwrap().into_carriers().unwrap();
assert_eq!(run.len(), 64);
assert_eq!(run.first().unwrap().carrier_index(), 64);
assert_eq!(run.last().unwrap().carrier_index(), 127);
drop(run);
drop(occupied);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn word_run_miss_leaves_fragmented_capacity_available() {
let (slot, _) = prepared_slot(192);
let mut occupied = BlockSlot::try_claim(&slot, CarrierCount::new(192))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
drop(occupied.drain(128..192).collect::<Vec<_>>());
drop(occupied.drain(0..64).collect::<Vec<_>>());
let claim = BlockSlot::try_claim_word_run(&slot, 0, 3, 2).unwrap();
assert_eq!(claim.inspected_words(), 3);
assert!(claim.into_provisional().is_none());
let fragmented = BlockSlot::try_claim(&slot, CarrierCount::new(128))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
assert_eq!(fragmented.len(), 128);
drop(fragmented);
drop(occupied);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn empty_claim_windows_do_not_mutate_ownership() {
let (slot, _) = prepared_slot(65);
let zero_budget = BlockSlot::try_claim_words(&slot, 0, 0, CarrierCount::new(1)).unwrap();
assert_eq!(zero_budget.inspected_words(), 0);
assert!(zero_budget.into_provisional().is_none());
let past_end =
BlockSlot::try_claim_words(&slot, slot.bitmap_words(), 1, CarrierCount::new(1))
.unwrap();
assert_eq!(past_end.inspected_words(), 0);
assert!(past_end.into_provisional().is_none());
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn inactive_window_consumes_scan_positions_without_claiming() {
let slot = Arc::new(BlockSlot::new(7, geometry(65)).unwrap());
let claim = BlockSlot::try_claim_words(&slot, 0, usize::MAX, CarrierCount::new(1)).unwrap();
assert_eq!(claim.inspected_words(), 2);
assert!(claim.into_provisional().is_none());
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn claim_never_wins_padding_bits() {
let (slot, _) = prepared_slot(65);
let carriers = BlockSlot::try_claim(&slot, CarrierCount::new(65))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
assert_eq!(carriers.len(), 65);
assert_eq!(carriers.last().unwrap().id().index, 64);
assert!(BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.is_none());
drop(carriers);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn dropping_provisional_bits_returns_every_word() {
let (slot, _) = prepared_slot(65);
let provisional = BlockSlot::try_claim(&slot, CarrierCount::new(65))
.unwrap()
.unwrap();
assert_eq!(slot.live_carriers(), 65);
drop(provisional);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn concurrent_attempts_clear_only_their_won_bits() {
let (slot, _) = prepared_slot(3);
let mut first = BlockClaimAttempt::begin(&slot).unwrap().unwrap();
let mut second = BlockClaimAttempt::begin(&slot).unwrap().unwrap();
assert_eq!(first.take(1), 1);
assert_eq!(second.take(2), 2);
let first = first.finish().unwrap();
let second = second.finish().unwrap();
assert_eq!(slot.live_carriers(), 3);
drop(first);
assert_eq!(slot.live_carriers(), 2);
drop(second);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn partial_claim_crosses_a_bitmap_word_boundary() {
let (slot, _) = prepared_slot(66);
let first = BlockSlot::try_claim(&slot, CarrierCount::new(63))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
let second = BlockSlot::try_claim(&slot, CarrierCount::new(3))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
assert_eq!(first.last().unwrap().id().index, 62);
assert_eq!(
second
.iter()
.map(|carrier| carrier.id().index)
.collect::<Vec<_>>(),
vec![63, 64, 65]
);
drop(first);
drop(second);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn provisional_word_bits_map_to_carrier_indices() {
let (slot, _) = prepared_slot(68);
let incarnation = {
let current = slot.current.load();
let incarnation = current.as_ref().expect("slot is prepared");
incarnation.in_use[1].store(0b1010, Ordering::Release);
BlockIncarnation::identity(incarnation)
};
let provisional = ProvisionalBits {
slot: Arc::clone(&slot),
incarnation,
won: vec![WonWord {
word_index: 1,
mask: 0b1010,
}],
};
let carriers = provisional.into_carriers().unwrap();
assert_eq!(
carriers
.iter()
.map(|carrier| carrier.id().index)
.collect::<Vec<_>>(),
vec![65, 67]
);
drop(carriers);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn dropping_unfinished_attempt_returns_original_bits() {
let (slot, _) = prepared_slot(2);
let mut attempt = BlockClaimAttempt::begin(&slot).unwrap().unwrap();
assert_eq!(attempt.take(2), 2);
assert_eq!(slot.live_carriers(), 2);
drop(attempt);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn trim_preserves_floor_and_abandons_for_live_ownership() {
let (slot, mut prepared) = prepared_slot(2);
assert!(matches!(
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::new(1)),
Err(TrimBlocked::FloorViolation)
));
assert_eq!(prepared, CarrierCount::new(2));
let carriers = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
assert!(matches!(
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO),
Err(TrimBlocked::Busy)
));
assert_eq!(prepared, CarrierCount::new(2));
assert_mapping(&slot, MappingState::Prepared);
drop(carriers);
}
#[test]
fn successful_trim_revives_with_fresh_metadata_at_the_same_address() {
let (slot, mut prepared) = prepared_slot(1);
let original_incarnation =
Arc::clone(slot.current.load().as_ref().expect("slot is prepared"));
let original_address = slot.range.base_address();
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
assert_eq!(cleanup.carrier_count(), CarrierCount::new(1));
assert_eq!(prepared, CarrierCount::ZERO);
assert!(BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.is_none());
cleanup.finish().unwrap();
assert_mapping(
&slot,
MappingState::Reserved {
reclaim_pending: false,
},
);
assert!(current_identity(&slot).is_none());
slot.prepare(&mut prepared).unwrap();
assert_eq!(prepared, CarrierCount::new(1));
assert_eq!(slot.range.base_address(), original_address);
let revived = slot.current.load();
assert!(!Arc::ptr_eq(
revived.as_ref().expect("slot was revived"),
&original_incarnation
));
}
#[test]
fn stale_failed_gate_rolls_back_only_retired_metadata() {
let (slot, mut prepared) = prepared_slot(1);
let mut stale = BlockClaimAttempt::begin(&slot).unwrap().unwrap();
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO)
.unwrap()
.finish()
.unwrap();
slot.prepare(&mut prepared).unwrap();
let current = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
assert_eq!(stale.take(1), 1);
assert!(stale.finish().is_none());
assert_eq!(slot.live_carriers(), 1);
drop(current);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn failed_deactivation_can_restore_the_draining_incarnation() {
let (slot, mut prepared) = prepared_slot(1);
let original_identity = current_identity(&slot).unwrap();
slot.range
.inject_failure_once(VirtualMemoryOperation::Deactivate);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
let error = cleanup.finish().unwrap_err();
assert!(matches!(
error,
CleanupRetry::DeactivationPending(ref error)
if error.operation() == VirtualMemoryOperation::Deactivate
));
assert_eq!(prepared, CarrierCount::ZERO);
assert_mapping(&slot, MappingState::DeactivationRecoveryPending);
assert_eq!(current_identity(&slot), Some(original_identity));
assert!(BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.is_none());
assert!(matches!(
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO),
Err(TrimBlocked::CleanupPending)
));
slot.prepare(&mut prepared).unwrap();
assert_eq!(prepared, CarrierCount::new(1));
assert_mapping(&slot, MappingState::Prepared);
assert_eq!(current_identity(&slot), Some(original_identity));
let carrier = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap();
drop(carrier);
}
#[test]
fn protection_retry_finishes_inactive_cleanup() {
let (slot, mut prepared) = prepared_slot(1);
slot.range
.inject_failure_once(VirtualMemoryOperation::Deactivate);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
assert!(matches!(
cleanup.finish(),
Err(CleanupRetry::DeactivationPending(_))
));
slot.retry_cleanup().unwrap();
assert_eq!(prepared, CarrierCount::ZERO);
assert_mapping(
&slot,
MappingState::Reserved {
reclaim_pending: false,
},
);
assert!(current_identity(&slot).is_none());
}
#[test]
fn failed_discard_retires_the_incarnation_and_retries_inactive() {
let (slot, mut prepared) = prepared_slot(1);
slot.range
.inject_failure_once(VirtualMemoryOperation::Discard);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
let error = cleanup.finish().unwrap_err();
assert!(matches!(
error,
CleanupRetry::ReclaimPending(ref error)
if error.operation() == VirtualMemoryOperation::Discard
));
assert_eq!(prepared, CarrierCount::ZERO);
assert_mapping(
&slot,
MappingState::Reserved {
reclaim_pending: true,
},
);
assert!(current_identity(&slot).is_none());
slot.retry_cleanup().unwrap();
assert_mapping(
&slot,
MappingState::Reserved {
reclaim_pending: false,
},
);
}
#[test]
fn revival_clears_pending_reclaim_before_publication() {
let (slot, mut prepared) = prepared_slot(1);
slot.range
.inject_failure_once(VirtualMemoryOperation::Discard);
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO)
.unwrap()
.finish()
.unwrap_err();
slot.prepare(&mut prepared).unwrap();
slot.retry_cleanup().unwrap();
assert_eq!(prepared, CarrierCount::new(1));
assert_mapping(&slot, MappingState::Prepared);
let carrier = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap();
drop(carrier);
}
#[test]
fn dropped_cleanup_completes_the_confirmed_trim() {
let (slot, mut prepared) = prepared_slot(1);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
drop(cleanup);
assert_eq!(prepared, CarrierCount::ZERO);
assert_mapping(
&slot,
MappingState::Reserved {
reclaim_pending: false,
},
);
assert!(current_identity(&slot).is_none());
}
#[test]
fn dropped_cleanup_leaves_failed_protection_nonclaimable() {
let (slot, mut prepared) = prepared_slot(1);
slot.range
.inject_failure_once(VirtualMemoryOperation::Deactivate);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
drop(cleanup);
assert_eq!(prepared, CarrierCount::ZERO);
assert_mapping(&slot, MappingState::DeactivationRecoveryPending);
assert!(current_identity(&slot).is_some());
assert!(BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.is_none());
}
#[test]
fn identity_mismatch_stops_before_clearing() {
let (slot, _) = prepared_slot(1);
let mut carriers = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
let carrier = carriers.pop().unwrap();
let wrong = CarrierId {
incarnation: IncarnationIdentity(
NonZeroUsize::new(carrier.id().incarnation.0.get().wrapping_add(1))
.unwrap_or(NonZeroUsize::MIN),
),
..carrier.id()
};
let result = catch_unwind(AssertUnwindSafe(|| slot.release_one(wrong)));
assert!(result.is_err());
assert_eq!(slot.live_carriers(), 1);
drop(carrier);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn slot_mismatch_stops_before_clearing() {
let (slot, _) = prepared_slot(1);
let mut carriers = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
let carrier = carriers.pop().unwrap();
let wrong = CarrierId {
slot: carrier.id().slot + 1,
..carrier.id()
};
let result = catch_unwind(AssertUnwindSafe(|| slot.release_one(wrong)));
assert!(result.is_err());
assert_eq!(slot.live_carriers(), 1);
drop(carrier);
assert_eq!(slot.live_carriers(), 0);
}
#[test]
fn selects_only_the_requested_low_bits() {
assert_eq!(take_lowest(0, 8), 0);
assert_eq!(take_lowest(0b1011_0100, 0), 0);
assert_eq!(take_lowest(0b1011_0100, 1), 0b0000_0100);
assert_eq!(take_lowest(0b1011_0100, 3), 0b0011_0100);
assert_eq!(take_lowest(0b1011_0100, usize::MAX), 0b1011_0100);
assert_eq!(take_lowest(u64::MAX, usize::MAX), u64::MAX);
}
#[test]
fn repeated_wins_in_one_word_share_one_record() {
let mut won = Vec::new();
record_won(&mut won, 1, 0b0001);
record_won(&mut won, 1, 0b0100);
record_won(&mut won, 2, 0b0010);
assert_eq!(won.len(), 2);
assert_eq!(won[0].word_index, 1);
assert_eq!(won[0].mask, 0b0101);
assert_eq!(won[1].word_index, 2);
assert_eq!(won[1].mask, 0b0010);
}
#[test]
#[cfg_attr(
miri,
ignore = "exhaustive pure-integer sweep adds no Miri-specific coverage"
)]
fn take_lowest_returns_exact_lowest_subset() {
fn assert_lowest_subset(available: u64, count: usize) {
let selected = take_lowest(available, count);
assert_eq!(
selected & !available,
0,
"selected unavailable bits from {available:#018x} with count {count}"
);
assert_eq!(
selected.count_ones() as usize,
count.min(available.count_ones() as usize),
"selected the wrong number of bits from {available:#018x} with count {count}"
);
let remaining = available & !selected;
if selected != 0 && remaining != 0 {
let highest_selected = u64::BITS - 1 - selected.leading_zeros();
let lowest_remaining = remaining.trailing_zeros();
assert!(
highest_selected < lowest_remaining,
"selected {selected:#018x} from {available:#018x} with count {count}"
);
}
}
for available in 0..=u16::MAX as u64 {
for count in 0..=(u16::BITS as usize + 1) {
assert_lowest_subset(available, count);
}
}
for available in [
1 << 63,
(1 << 63) | 1,
0x8000_0000_0000_00a5,
0xaaaa_aaaa_aaaa_aaaa,
0x5555_5555_5555_5555,
u64::MAX,
] {
for count in 0..=(u64::BITS as usize + 1) {
assert_lowest_subset(available, count);
}
}
}
#[test]
fn zero_claim_is_rejected_without_mutation() {
let (slot, _) = prepared_slot(1);
assert!(matches!(
BlockSlot::try_claim(&slot, CarrierCount::ZERO),
Err(BlockError::InvalidClaimCount)
));
assert_eq!(slot.live_carriers(), 0);
}
fn assert_send_sync<T: Send + Sync>() {}
#[test]
fn ownership_spine_is_send_and_sync() {
assert_send_sync::<BlockSlot>();
assert_send_sync::<CarrierAllocation>();
}
}
#[cfg(all(test, s3_tm_loom))]
mod loom_tests {
use super::super::virtual_memory::VirtualMemoryOperation;
use super::*;
use crate::runtime::sync::sync::atomic::{AtomicBool, Ordering};
use crate::runtime::sync::thread;
fn prepared_slot() -> (Arc<BlockSlot>, CarrierCount) {
let geometry = PoolGeometry::new(4096, 4096, 4096).unwrap();
let slot = Arc::new(BlockSlot::new(0, geometry).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
(slot, prepared)
}
#[test]
fn stale_claim_cannot_clear_a_revived_claim() {
loom::model(|| {
let (slot, initial_prepared) = prepared_slot();
let loaded = Arc::new(AtomicBool::new(false));
let revived = Arc::new(AtomicBool::new(false));
let stale_slot = Arc::clone(&slot);
let stale_loaded = Arc::clone(&loaded);
let stale_revived = Arc::clone(&revived);
let stale = thread::spawn(move || {
let mut attempt = BlockClaimAttempt::begin(&stale_slot).unwrap().unwrap();
stale_loaded.store(true, Ordering::Release);
while !stale_revived.load(Ordering::Acquire) {
loom::thread::yield_now();
}
assert_eq!(attempt.take(1), 1);
assert!(attempt.finish().is_none());
});
let current_slot = Arc::clone(&slot);
let current_loaded = Arc::clone(&loaded);
let current_revived = Arc::clone(&revived);
let current = thread::spawn(move || {
while !current_loaded.load(Ordering::Acquire) {
loom::thread::yield_now();
}
let mut prepared = initial_prepared;
BlockSlot::start_trim(¤t_slot, &mut prepared, CarrierCount::ZERO)
.unwrap()
.finish()
.unwrap();
current_slot.prepare(&mut prepared).unwrap();
let carrier = BlockSlot::try_claim(¤t_slot, CarrierCount::new(1))
.unwrap()
.unwrap()
.into_carriers()
.unwrap()
.pop()
.unwrap();
current_revived.store(true, Ordering::Release);
carrier
});
stale.join().unwrap();
let carrier = current.join().unwrap();
assert_eq!(slot.live_carriers(), 1);
drop(carrier);
assert_eq!(slot.live_carriers(), 0);
});
}
#[test]
fn claim_and_protection_recovery_preserve_single_ownership() {
loom::model(|| {
let (slot, mut prepared) = prepared_slot();
let original = Arc::clone(slot.current.load().as_ref().expect("slot is prepared"));
let mut attempt = BlockClaimAttempt::begin(&slot).unwrap().unwrap();
slot.range
.inject_failure_once(VirtualMemoryOperation::Deactivate);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
assert!(matches!(
cleanup.finish(),
Err(CleanupRetry::DeactivationPending(_))
));
assert_eq!(attempt.take(1), 1);
let stale = thread::spawn(move || attempt.finish());
let recovery_slot = Arc::clone(&slot);
let recovery = thread::spawn(move || {
recovery_slot.prepare(&mut prepared).unwrap();
let current = BlockSlot::try_claim(&recovery_slot, CarrierCount::new(1)).unwrap();
(prepared, current)
});
let stale = stale.join().unwrap();
let (prepared, current) = recovery.join().unwrap();
let owned = stale
.as_ref()
.map_or(0, |claim| claim.len().get())
.checked_add(current.as_ref().map_or(0, |claim| claim.len().get()))
.unwrap();
assert_eq!(prepared, CarrierCount::new(1));
assert!(matches!(*slot.mapping.lock(), MappingState::Prepared));
let restored = slot.current.load();
assert!(Arc::ptr_eq(
restored.as_ref().expect("incarnation was restored"),
&original
));
assert!(owned <= 1);
assert_eq!(slot.live_carriers(), owned);
drop(stale);
drop(current);
assert_eq!(slot.live_carriers(), 0);
});
}
#[test]
fn claim_and_trim_cannot_both_pass_the_gate() {
loom::model(|| {
let (slot, initial_prepared) = prepared_slot();
let prepared = Arc::new(Mutex::new(initial_prepared));
let claim_slot = Arc::clone(&slot);
let claim = thread::spawn(move || {
BlockSlot::try_claim(&claim_slot, CarrierCount::new(1))
.unwrap()
.map(ProvisionalBits::into_carriers)
.transpose()
.unwrap()
});
let trim_slot = Arc::clone(&slot);
let trim_prepared = Arc::clone(&prepared);
let trim = thread::spawn(move || {
let start = {
let mut prepared = trim_prepared.lock();
BlockSlot::start_trim(&trim_slot, &mut prepared, CarrierCount::ZERO)
};
match start {
Ok(cleanup) => {
cleanup.finish().unwrap();
true
}
Err(TrimBlocked::Busy) => false,
Err(other) => panic!("unexpected trim result: {other:?}"),
}
});
let carriers = claim.join().unwrap();
let trimmed = trim.join().unwrap();
if let Some(carriers) = carriers {
assert!(!trimmed);
drop(carriers);
}
let active = slot
.current
.load()
.as_ref()
.map(|incarnation| {
incarnation.state.load(Ordering::Acquire) == IncarnationState::Active
})
.unwrap_or(false);
if active {
let mut prepared = prepared.lock();
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO)
.unwrap()
.finish()
.unwrap();
}
assert!(slot.current.load().as_ref().is_none());
assert_eq!(
*slot.mapping.lock(),
MappingState::Reserved {
reclaim_pending: false
}
);
});
}
#[test]
fn preclaimed_activation_publishes_owned_bits_before_fast_claim() {
loom::model(|| {
let geometry = PoolGeometry::new(4096, 8192, 4096).unwrap();
let slot = Arc::new(BlockSlot::new(0, geometry).unwrap());
let prepare_slot = Arc::clone(&slot);
let prepare = thread::spawn(move || {
let mut prepared = CarrierCount::ZERO;
let carriers = BlockSlot::prepare_and_claim_if_inactive(
&prepare_slot,
&mut prepared,
CarrierCount::new(1),
)
.unwrap()
.expect("fresh slot should activate")
.into_carriers()
.unwrap();
(prepared, carriers)
});
let claim_slot = Arc::clone(&slot);
let claim = thread::spawn(move || {
BlockSlot::try_claim(&claim_slot, CarrierCount::new(1))
.unwrap()
.map(ProvisionalBits::into_carriers)
.transpose()
.unwrap()
});
let (prepared, preclaimed) = prepare.join().unwrap();
let claimed = claim.join().unwrap();
assert_eq!(prepared, CarrierCount::new(2));
assert_eq!(preclaimed.len(), 1);
assert_eq!(preclaimed[0].id().index, 0);
if let Some(claimed) = &claimed {
assert_eq!(claimed.len(), 1);
assert_eq!(claimed[0].id().index, 1);
}
let expected_live = 1 + claimed.as_ref().map_or(0, Vec::len);
assert_eq!(slot.live_carriers(), expected_live);
drop(preclaimed);
drop(claimed);
assert_eq!(slot.live_carriers(), 0);
});
}
#[test]
fn exhaustive_claim_retries_after_an_optimistic_collision() {
loom::model(|| {
let geometry = PoolGeometry::new(4096, 8192, 4096).unwrap();
let slot = Arc::new(BlockSlot::new(0, geometry).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
let exhaustive_slot = Arc::clone(&slot);
let exhaustive = thread::spawn(move || {
BlockSlot::try_claim_exhaustive(&exhaustive_slot, CarrierCount::new(1))
.unwrap()
.expect("exhaustive claim must find one of two carriers")
.into_carriers()
.unwrap()
});
let optimistic_slot = Arc::clone(&slot);
let optimistic = thread::spawn(move || {
BlockSlot::try_claim(&optimistic_slot, CarrierCount::new(1))
.unwrap()
.map(ProvisionalBits::into_carriers)
.transpose()
.unwrap()
});
let exhaustive = exhaustive.join().unwrap();
let optimistic = optimistic.join().unwrap();
if let Some(optimistic) = &optimistic {
assert_ne!(exhaustive[0].carrier_index(), optimistic[0].carrier_index());
}
assert_eq!(
slot.live_carriers(),
1 + optimistic.as_ref().map_or(0, Vec::len)
);
drop(exhaustive);
drop(optimistic);
assert_eq!(slot.live_carriers(), 0);
});
}
#[test]
fn two_claimants_cannot_own_one_carrier() {
loom::model(|| {
let (slot, _) = prepared_slot();
let first_slot = Arc::clone(&slot);
let first = thread::spawn(move || {
BlockSlot::try_claim(&first_slot, CarrierCount::new(1)).unwrap()
});
let second_slot = Arc::clone(&slot);
let second = thread::spawn(move || {
BlockSlot::try_claim(&second_slot, CarrierCount::new(1)).unwrap()
});
let first = first.join().unwrap();
let second = second.join().unwrap();
let owned = first.as_ref().map_or(0, |claim| claim.len().get())
+ second.as_ref().map_or(0, |claim| claim.len().get());
assert_eq!(owned, 1);
assert_eq!(slot.live_carriers(), 1);
drop(first);
drop(second);
assert_eq!(slot.live_carriers(), 0);
});
}
#[test]
fn word_run_collision_rolls_back_every_partial_win() {
loom::model(|| {
let geometry = PoolGeometry::new(4096, 128 * 4096, 4096).unwrap();
let slot = Arc::new(BlockSlot::new(0, geometry).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
let run_slot = Arc::clone(&slot);
let run = thread::spawn(move || {
BlockSlot::try_claim_word_run(&run_slot, 0, 2, 2)
.unwrap()
.into_provisional()
.map(ProvisionalBits::into_carriers)
.transpose()
.unwrap()
});
let tail_slot = Arc::clone(&slot);
let tail = thread::spawn(move || {
BlockSlot::try_claim_words(&tail_slot, 1, 1, CarrierCount::new(64))
.unwrap()
.into_provisional()
.map(ProvisionalBits::into_carriers)
.transpose()
.unwrap()
});
let run = run.join().unwrap();
let tail = tail.join().unwrap();
match (&run, &tail) {
(Some(run), None) => {
assert_eq!(run.len(), 128);
assert_eq!(slot.live_carriers(), 128);
}
(None, Some(tail)) => {
assert_eq!(tail.len(), 64);
assert!(tail.iter().all(|carrier| carrier.carrier_index() >= 64));
assert_eq!(slot.live_carriers(), 64);
}
_ => panic!("overlapping whole-word claims published an invalid result"),
}
drop(run);
drop(tail);
assert_eq!(slot.live_carriers(), 0);
});
}
#[test]
fn concurrent_returns_clear_disjoint_bits_in_one_word() {
loom::model(|| {
let geometry = PoolGeometry::new(4096, 8192, 4096).unwrap();
let slot = Arc::new(BlockSlot::new(0, geometry).unwrap());
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
let carriers = BlockSlot::try_claim(&slot, CarrierCount::new(2))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
let mut carriers = carriers.into_iter();
let first = carriers.next().unwrap();
let second = carriers.next().unwrap();
assert!(carriers.next().is_none());
let first = thread::spawn(move || drop(first));
let second = thread::spawn(move || drop(second));
first.join().unwrap();
second.join().unwrap();
assert_eq!(slot.live_carriers(), 0);
});
}
}