use std::collections::TryReserveError;
use std::fmt;
use std::sync::atomic::{AtomicU64, Ordering as DiagnosticOrdering};
use super::admission::AdmissionGuard;
use super::block::{
BlockError, BlockSlot, CarrierAllocation, ProvisionalBits, TrimBlocked, TrimCleanup,
};
use super::geometry::PoolGeometry;
use super::virtual_memory::VirtualMemoryOperation;
use super::{invariant_violation, CarrierCount};
use crate::runtime::sync::sync::atomic::{AtomicUsize, Ordering};
use crate::runtime::sync::sync::{Arc, Mutex};
pub(super) struct Arena {
geometry: PoolGeometry,
optimistic_scan_words: usize,
scan_origin: AtomicUsize,
diagnostics: Arc<ArenaDiagnostics>,
registry: BlockRegistry,
state: Mutex<ArenaState>,
#[cfg(test)]
enable_guard_pages: bool,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) struct ArenaOptions {
optimistic_scan_words: usize,
enable_detailed_counters: bool,
#[cfg(test)]
enable_guard_pages: bool,
}
impl ArenaOptions {
pub(super) fn new(optimistic_scan_words: usize, enable_detailed_counters: bool) -> Self {
Self {
optimistic_scan_words,
enable_detailed_counters,
#[cfg(test)]
enable_guard_pages: false,
}
}
pub(super) fn optimistic_scan_words(self) -> usize {
self.optimistic_scan_words
}
#[cfg(test)]
pub(super) fn enable_guard_pages(mut self) -> Self {
self.enable_guard_pages = true;
self
}
}
impl Arena {
pub(super) fn new(geometry: PoolGeometry, options: ArenaOptions) -> Result<Self, ArenaError> {
let optimistic_scan_words = options.optimistic_scan_words;
if optimistic_scan_words == 0 {
return Err(ArenaError::InvalidScanBudget);
}
Ok(Self {
geometry,
optimistic_scan_words,
scan_origin: AtomicUsize::new(0),
diagnostics: Arc::new(ArenaDiagnostics::new(options.enable_detailed_counters)),
registry: BlockRegistry::new(),
state: Mutex::new(ArenaState {
slots: Vec::new(),
next_slot: Some(0),
}),
#[cfg(test)]
enable_guard_pages: options.enable_guard_pages,
})
}
#[cfg(test)]
pub(super) fn reserve_slot(&self) -> Result<Arc<BlockSlot>, ArenaError> {
let mut state = self.state.lock();
self.reserve_slot_locked(&mut state)
}
fn reserve_slot_locked(&self, state: &mut ArenaState) -> Result<Arc<BlockSlot>, ArenaError> {
let slot_id = state.next_slot.ok_or(ArenaError::SlotIdExhausted)?;
state.slots.try_reserve(1)?;
let slot = Arc::new(self.new_slot(slot_id)?);
let generation = RegistryGeneration::try_with_slot(&state.slots, &slot)?;
state.slots.push(Arc::clone(&slot));
state.next_slot = slot_id.checked_add(1);
self.registry.publish(generation);
self.diagnostics.record_block_range_reserved();
Ok(slot)
}
fn new_slot(&self, slot_id: u32) -> Result<BlockSlot, BlockError> {
#[cfg(test)]
if self.enable_guard_pages {
return BlockSlot::new_guarded(slot_id, self.geometry);
}
BlockSlot::new(slot_id, self.geometry)
}
pub(super) fn classify_range(&self, start: usize, len: usize) -> Option<ClassifiedRange> {
self.registry.load().classify_range(start, len)
}
pub(super) fn select_trim_candidate(&self) -> Option<Arc<BlockSlot>> {
let generation = self.registry_generation();
let mut scanned = 0;
let candidate = generation.slots_in_claim_order().iter().find_map(|slot| {
scanned += 1;
slot.appears_free().then(|| Arc::clone(slot))
});
self.diagnostics.record_trim_slots_scanned(scanned);
candidate
}
pub(super) fn start_trim(
&self,
admission: &mut AdmissionGuard<'_>,
floor: CarrierCount,
) -> ArenaTrim {
let generation = self.registry_generation();
let mut scanned = 0;
let mut result = ArenaTrim::Blocked;
for slot in generation.slots_in_claim_order() {
scanned += 1;
if !slot.appears_free() {
continue;
}
match BlockSlot::start_trim(slot, admission.prepared_capacity_mut(), floor) {
Ok(cleanup) => {
result = ArenaTrim::Started(cleanup);
break;
}
Err(TrimBlocked::FloorViolation) => break,
Err(TrimBlocked::NotPrepared | TrimBlocked::Busy | TrimBlocked::CleanupPending) => {
}
}
}
self.diagnostics.record_trim_slots_scanned(scanned);
result
}
pub(super) fn retry_cleanup(&self) -> bool {
let generation = self.registry_generation();
let mut complete = true;
for slot in generation.slots_in_claim_order() {
match slot.retry_cleanup() {
Ok(false) => {}
Ok(true) => self.diagnostics.record_cleanup_retry(),
Err(error) => {
self.diagnostics.record_cleanup_retry();
self.diagnostics.record_cleanup_failure();
tracing::warn!(
target: crate::telemetry::TARGET_MEMORY,
slot_id = slot.id(),
error = ?error,
"buffer-pool mapping cleanup retry failed"
);
complete = false;
}
}
}
complete
}
pub(super) fn record_block_reclaimed(&self) {
self.diagnostics.record_block_reclaimed();
}
pub(super) fn diagnostics(&self) -> ArenaDiagnosticSnapshot {
self.diagnostics.snapshot()
}
pub(super) fn sample_lifecycle(&self) -> ArenaLifecycleSample {
let generation = self.registry_generation();
let mut sample = ArenaLifecycleSample::default();
for slot in generation.slots_in_claim_order() {
let block = slot.sample_lifecycle();
sample.prepared_capacity = sample
.prepared_capacity
.checked_add(block.prepared_capacity)
.unwrap_or_else(|| invariant_violation("arena prepared diagnostic overflow"));
sample.live_carriers = sample
.live_carriers
.checked_add(block.live_carriers)
.unwrap_or_else(|| invariant_violation("arena live diagnostic overflow"));
if block.cleanup_pending {
sample.cleanup_pending_blocks = sample
.cleanup_pending_blocks
.checked_add(1)
.unwrap_or_else(|| invariant_violation("arena cleanup diagnostic overflow"));
}
}
sample
}
#[cfg(any(test, s3_tm_fuzz))]
pub(super) fn has_free_word_run_quiescent(&self, word_count: usize) -> bool {
let generation = self.registry_generation();
generation
.slots_in_claim_order()
.iter()
.any(|slot| slot.has_free_word_run_quiescent(word_count))
}
pub(super) fn prepare_to(
&self,
admission: &mut AdmissionGuard<'_>,
target: CarrierCount,
) -> Result<(), ArenaError> {
if admission.prepared_capacity() >= target {
return Ok(());
}
let mut state = self.state.lock();
for slot in &state.slots {
if admission.prepared_capacity() >= target {
return Ok(());
}
match slot.prepare(admission.prepared_capacity_mut()) {
Ok(()) => self.diagnostics.record_block_prepared(),
Err(BlockError::AlreadyPrepared) => {}
Err(error) => return Err(error.into()),
}
}
while admission.prepared_capacity() < target {
let slot = self.reserve_slot_locked(&mut state)?;
slot.prepare(admission.prepared_capacity_mut())?;
self.diagnostics.record_block_prepared();
}
Ok(())
}
pub(super) fn claim_optimistic(
&self,
required: CarrierCount,
) -> Result<ClaimBatch, ArenaError> {
if required == CarrierCount::ZERO {
return Err(ArenaError::InvalidClaimCount);
}
let generation = self.registry_generation();
let slots = generation.slots_in_claim_order();
let words_per_slot = self.geometry.bitmap_words();
let total_positions =
slots
.len()
.checked_mul(words_per_slot)
.ok_or(ArenaError::ScanSpaceOverflow {
slots: slots.len(),
words_per_slot,
})?;
let mut batch = ClaimBatch::new(required, Arc::clone(&self.diagnostics));
if total_positions == 0 {
self.diagnostics.record_optimistic_scan(0, true);
return Ok(batch);
}
let budget = self.optimistic_scan_words.min(total_positions);
let origin_stride = if budget == total_positions { 1 } else { budget };
let origin = self.scan_origin.fetch_add(origin_stride, Ordering::Relaxed) % total_positions;
if let Some(word_count) = self.contiguous_word_count(required) {
if word_count > budget {
self.diagnostics.record_optimistic_scan(0, true);
return Ok(batch);
}
while batch.inspected_words < budget && !batch.is_complete() {
let position = wrapped_position(origin, batch.inspected_words, total_positions);
let slot_index = position / words_per_slot;
let start_word = position % words_per_slot;
let word_limit = (words_per_slot - start_word).min(budget - batch.inspected_words);
let claim = BlockSlot::try_claim_word_run(
&slots[slot_index],
start_word,
word_limit,
word_count,
)?;
let inspected = claim.inspected_words();
if inspected == 0 || inspected > word_limit {
invariant_violation("contiguous block claim reported invalid scan work");
}
batch.inspected_words += inspected;
if let Some(provisional) = claim.into_provisional() {
batch.push(provisional)?;
}
}
self.diagnostics
.record_optimistic_scan(batch.inspected_words, !batch.is_complete());
return Ok(batch);
}
while batch.inspected_words < budget && !batch.is_complete() {
let position = wrapped_position(origin, batch.inspected_words, total_positions);
let slot_index = position / words_per_slot;
let start_word = position % words_per_slot;
let word_limit = (words_per_slot - start_word).min(budget - batch.inspected_words);
let claim = BlockSlot::try_claim_words(
&slots[slot_index],
start_word,
word_limit,
batch.remaining(),
)?;
let inspected = claim.inspected_words();
if inspected == 0 || inspected > word_limit {
invariant_violation("bounded block claim reported invalid scan work");
}
batch.inspected_words += inspected;
if let Some(provisional) = claim.into_provisional() {
batch.push(provisional)?;
}
}
self.diagnostics
.record_optimistic_scan(batch.inspected_words, !batch.is_complete());
Ok(batch)
}
pub(super) fn complete_claim_serialized(
&self,
admission: &mut AdmissionGuard<'_>,
batch: &mut ClaimBatch,
) -> Result<(), ArenaError> {
if batch.is_complete() {
return Ok(());
}
self.diagnostics.record_serialized_fallback();
let mut tracker = SerializedFallbackTracker::new(self.diagnostics.as_ref());
let mut state = self.state.lock();
if batch.claimed() == CarrierCount::ZERO {
if let Some(word_count) = self.contiguous_word_count(batch.required) {
let slot_count = state.slots.len();
if slot_count != 0 {
let words_per_slot = self.geometry.bitmap_words();
let start_slot =
(self.scan_origin.load(Ordering::Relaxed) / words_per_slot) % slot_count;
for offset in 0..slot_count {
let slot = &state.slots[(start_slot + offset) % slot_count];
tracker.record_slot_inspected();
let claim =
BlockSlot::try_claim_word_run(slot, 0, words_per_slot, word_count)?;
if let Some(provisional) = claim.into_provisional() {
batch.push(provisional)?;
return Ok(());
}
}
}
}
}
for slot in &state.slots {
if batch.is_complete() {
return Ok(());
}
tracker.record_slot_inspected();
if let Some(provisional) = BlockSlot::try_claim_exhaustive(slot, batch.remaining())? {
batch.push(provisional)?;
}
}
for slot in &state.slots {
if batch.is_complete() {
return Ok(());
}
tracker.record_slot_inspected();
let count = std::cmp::min(batch.remaining(), slot.carrier_count());
if let Some(provisional) = BlockSlot::prepare_and_claim_if_inactive(
slot,
admission.prepared_capacity_mut(),
count,
)? {
self.diagnostics.record_block_prepared();
batch.push(provisional)?;
}
}
while !batch.is_complete() {
let slot = self.reserve_slot_locked(&mut state)?;
let count = std::cmp::min(batch.remaining(), slot.carrier_count());
let provisional = BlockSlot::prepare_and_claim_if_inactive(
&slot,
admission.prepared_capacity_mut(),
count,
)?
.unwrap_or_else(|| {
invariant_violation("new arena slot was not reusable for private growth")
});
self.diagnostics.record_block_prepared();
batch.push(provisional)?;
}
Ok(())
}
fn contiguous_word_count(&self, count: CarrierCount) -> Option<usize> {
if count == CarrierCount::ZERO
|| count > self.geometry.carriers_per_block()
|| !count.get().is_multiple_of(u64::BITS as usize)
{
return None;
}
Some(count.get() / u64::BITS as usize)
}
fn registry_generation(&self) -> RegistryGenerationGuard {
self.registry.load()
}
}
#[derive(Debug)]
pub(super) enum ArenaError {
Block(BlockError),
Allocation(TryReserveError),
InvalidScanBudget,
InvalidClaimCount,
ScanSpaceOverflow {
slots: usize,
words_per_slot: usize,
},
IncompleteClaim {
required: usize,
claimed: usize,
},
SlotIdExhausted,
RegistryCapacityOverflow,
AddressOverflow {
slot_id: u32,
start: usize,
len: usize,
},
AddressOverlap {
first_start: usize,
first_end: usize,
second_start: usize,
second_end: usize,
},
}
impl ArenaError {
pub(super) fn cleanup_required(&self) -> bool {
matches!(
self,
Self::Block(BlockError::VirtualMemory(error))
if error.operation() == VirtualMemoryOperation::Prepare
)
}
}
impl fmt::Display for ArenaError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Block(error) => error.fmt(f),
Self::Allocation(error) => write!(f, "arena metadata allocation failed: {error}"),
Self::InvalidScanBudget => f.write_str("arena optimistic scan budget must be nonzero"),
Self::InvalidClaimCount => f.write_str("an arena claim must request carriers"),
Self::ScanSpaceOverflow {
slots,
words_per_slot,
} => write!(
f,
"arena scan space {slots} slots by {words_per_slot} words overflows"
),
Self::IncompleteClaim { required, claimed } => write!(
f,
"cannot finish incomplete arena claim: required {required}, claimed {claimed}"
),
Self::SlotIdExhausted => f.write_str("arena block identifier space is exhausted"),
Self::RegistryCapacityOverflow => f.write_str("arena registry capacity would overflow"),
Self::AddressOverflow {
slot_id,
start,
len,
} => write!(
f,
"block slot {slot_id} address range {start:#x}+{len:#x} overflows"
),
Self::AddressOverlap {
first_start,
first_end,
second_start,
second_end,
} => write!(
f,
"block ranges {first_start:#x}..{first_end:#x} and \
{second_start:#x}..{second_end:#x} overlap"
),
}
}
}
impl std::error::Error for ArenaError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::Block(error) => Some(error),
Self::Allocation(error) => Some(error),
Self::InvalidScanBudget
| Self::InvalidClaimCount
| Self::ScanSpaceOverflow { .. }
| Self::IncompleteClaim { .. }
| Self::SlotIdExhausted
| Self::RegistryCapacityOverflow
| Self::AddressOverflow { .. }
| Self::AddressOverlap { .. } => None,
}
}
}
impl From<BlockError> for ArenaError {
fn from(error: BlockError) -> Self {
Self::Block(error)
}
}
impl From<TryReserveError> for ArenaError {
fn from(error: TryReserveError) -> Self {
Self::Allocation(error)
}
}
#[must_use = "dropping a claim batch returns its provisional carrier bits"]
pub(super) struct ClaimBatch {
required: CarrierCount,
claimed: CarrierCount,
inspected_words: usize,
blocks: Vec<ProvisionalBits>,
diagnostics: Arc<ArenaDiagnostics>,
}
impl ClaimBatch {
fn new(required: CarrierCount, diagnostics: Arc<ArenaDiagnostics>) -> Self {
Self {
required,
claimed: CarrierCount::ZERO,
inspected_words: 0,
blocks: Vec::new(),
diagnostics,
}
}
#[cfg(test)]
pub(super) fn required(&self) -> CarrierCount {
self.required
}
pub(super) fn claimed(&self) -> CarrierCount {
self.claimed
}
pub(super) fn remaining(&self) -> CarrierCount {
self.required
.checked_sub(self.claimed)
.unwrap_or_else(|| invariant_violation("arena claim exceeds its required count"))
}
pub(super) fn inspected_words(&self) -> usize {
self.inspected_words
}
pub(super) fn is_complete(&self) -> bool {
self.claimed == self.required
}
fn push(&mut self, provisional: ProvisionalBits) -> Result<(), ArenaError> {
let next_claimed = self
.claimed
.checked_add(provisional.len())
.unwrap_or_else(|| invariant_violation("arena claim count overflowed"));
if next_claimed > self.required {
invariant_violation("arena claim won more carriers than requested");
}
if let Err(error) = self.blocks.try_reserve(1) {
self.diagnostics
.record_rolled_back_carriers(provisional.len().get());
return Err(error.into());
}
self.blocks.push(provisional);
self.claimed = next_claimed;
Ok(())
}
pub(super) fn finish(mut self) -> Result<Vec<CarrierAllocation>, ArenaError> {
if !self.is_complete() {
return Err(ArenaError::IncompleteClaim {
required: self.required.get(),
claimed: self.claimed.get(),
});
}
let mut carriers = Vec::new();
carriers.try_reserve_exact(self.required.get())?;
for provisional in self.blocks.drain(..) {
let mut block = provisional.into_carriers()?;
carriers.append(&mut block);
}
if carriers.len() != self.required.get() {
invariant_violation("complete arena claim converted the wrong carrier count");
}
self.claimed = CarrierCount::ZERO;
Ok(carriers)
}
}
impl Drop for ClaimBatch {
fn drop(&mut self) {
self.diagnostics
.record_rolled_back_carriers(self.claimed.get());
}
}
struct ArenaDiagnostics {
optimistic_misses: AtomicU64,
serialized_fallbacks: AtomicU64,
serialized_slots_inspected: AtomicU64,
blocks_prepared: AtomicU64,
block_ranges_reserved: AtomicU64,
rolled_back_carriers: AtomicU64,
trim_slots_scanned: AtomicU64,
blocks_reclaimed: AtomicU64,
cleanup_retries: AtomicU64,
cleanup_failures: AtomicU64,
detailed: Option<DetailedScanCounters>,
}
#[derive(Default)]
struct DetailedScanCounters {
optimistic_scans: AtomicU64,
optimistic_scan_words: AtomicU64,
}
impl ArenaDiagnostics {
fn new(enable_detailed_counters: bool) -> Self {
Self {
optimistic_misses: AtomicU64::new(0),
serialized_fallbacks: AtomicU64::new(0),
serialized_slots_inspected: AtomicU64::new(0),
blocks_prepared: AtomicU64::new(0),
block_ranges_reserved: AtomicU64::new(0),
rolled_back_carriers: AtomicU64::new(0),
trim_slots_scanned: AtomicU64::new(0),
blocks_reclaimed: AtomicU64::new(0),
cleanup_retries: AtomicU64::new(0),
cleanup_failures: AtomicU64::new(0),
detailed: enable_detailed_counters.then(DetailedScanCounters::default),
}
}
fn record_optimistic_scan(&self, words: usize, missed: bool) {
if let Some(detailed) = &self.detailed {
saturating_add(&detailed.optimistic_scans, 1);
saturating_add(&detailed.optimistic_scan_words, diagnostic_count(words));
}
if missed {
saturating_add(&self.optimistic_misses, 1);
}
}
fn record_serialized_fallback(&self) {
saturating_add(&self.serialized_fallbacks, 1);
}
fn record_serialized_slots_inspected(&self, slots: usize) {
saturating_add(&self.serialized_slots_inspected, diagnostic_count(slots));
}
fn record_block_prepared(&self) {
saturating_add(&self.blocks_prepared, 1);
}
fn record_block_range_reserved(&self) {
saturating_add(&self.block_ranges_reserved, 1);
}
fn record_rolled_back_carriers(&self, carriers: usize) {
saturating_add(&self.rolled_back_carriers, diagnostic_count(carriers));
}
fn record_trim_slots_scanned(&self, slots: usize) {
saturating_add(&self.trim_slots_scanned, diagnostic_count(slots));
}
fn record_block_reclaimed(&self) {
saturating_add(&self.blocks_reclaimed, 1);
}
fn record_cleanup_retry(&self) {
saturating_add(&self.cleanup_retries, 1);
}
fn record_cleanup_failure(&self) {
saturating_add(&self.cleanup_failures, 1);
}
fn snapshot(&self) -> ArenaDiagnosticSnapshot {
ArenaDiagnosticSnapshot {
optimistic_misses: self.optimistic_misses.load(DiagnosticOrdering::Relaxed),
serialized_fallbacks: self.serialized_fallbacks.load(DiagnosticOrdering::Relaxed),
serialized_slots_inspected: self
.serialized_slots_inspected
.load(DiagnosticOrdering::Relaxed),
blocks_prepared: self.blocks_prepared.load(DiagnosticOrdering::Relaxed),
block_ranges_reserved: self.block_ranges_reserved.load(DiagnosticOrdering::Relaxed),
rolled_back_carriers: self.rolled_back_carriers.load(DiagnosticOrdering::Relaxed),
trim_slots_scanned: self.trim_slots_scanned.load(DiagnosticOrdering::Relaxed),
blocks_reclaimed: self.blocks_reclaimed.load(DiagnosticOrdering::Relaxed),
cleanup_retries: self.cleanup_retries.load(DiagnosticOrdering::Relaxed),
cleanup_failures: self.cleanup_failures.load(DiagnosticOrdering::Relaxed),
detailed: self.detailed.as_ref().map(DetailedScanCounters::snapshot),
}
}
}
impl DetailedScanCounters {
fn snapshot(&self) -> DetailedScanSnapshot {
DetailedScanSnapshot {
optimistic_scans: self.optimistic_scans.load(DiagnosticOrdering::Relaxed),
optimistic_scan_words: self.optimistic_scan_words.load(DiagnosticOrdering::Relaxed),
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) struct ArenaDiagnosticSnapshot {
pub(super) optimistic_misses: u64,
pub(super) serialized_fallbacks: u64,
pub(super) serialized_slots_inspected: u64,
pub(super) blocks_prepared: u64,
pub(super) block_ranges_reserved: u64,
pub(super) rolled_back_carriers: u64,
pub(super) trim_slots_scanned: u64,
pub(super) blocks_reclaimed: u64,
pub(super) cleanup_retries: u64,
pub(super) cleanup_failures: u64,
pub(super) detailed: Option<DetailedScanSnapshot>,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) struct DetailedScanSnapshot {
pub(super) optimistic_scans: u64,
pub(super) optimistic_scan_words: u64,
}
struct SerializedFallbackTracker<'a> {
diagnostics: &'a ArenaDiagnostics,
slots_inspected: usize,
}
impl<'a> SerializedFallbackTracker<'a> {
fn new(diagnostics: &'a ArenaDiagnostics) -> SerializedFallbackTracker<'a> {
Self {
diagnostics,
slots_inspected: 0,
}
}
fn record_slot_inspected(&mut self) {
self.slots_inspected = self
.slots_inspected
.checked_add(1)
.unwrap_or_else(|| invariant_violation("serialized slot count overflowed"));
}
}
impl Drop for SerializedFallbackTracker<'_> {
fn drop(&mut self) {
self.diagnostics
.record_serialized_slots_inspected(self.slots_inspected);
}
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub(super) struct ArenaLifecycleSample {
pub(super) prepared_capacity: CarrierCount,
pub(super) live_carriers: CarrierCount,
pub(super) cleanup_pending_blocks: usize,
}
pub(super) enum ArenaTrim {
Started(TrimCleanup),
Blocked,
}
fn saturating_add(counter: &AtomicU64, value: u64) {
if value == 0 {
return;
}
#[allow(deprecated)]
let _ = counter.fetch_update(
DiagnosticOrdering::Relaxed,
DiagnosticOrdering::Relaxed,
|current| Some(current.saturating_add(value)),
);
}
fn diagnostic_count(value: usize) -> u64 {
u64::try_from(value).unwrap_or(u64::MAX)
}
fn wrapped_position(origin: usize, offset: usize, len: usize) -> usize {
let tail = len - origin;
if offset < tail {
origin + offset
} else {
offset - tail
}
}
struct ArenaState {
slots: Vec<Arc<BlockSlot>>,
next_slot: Option<u32>,
}
struct BlockRegistry {
current: registry_cell::RegistryCell,
}
impl BlockRegistry {
fn new() -> Self {
Self {
current: registry_cell::RegistryCell::new(Arc::new(RegistryGeneration::empty())),
}
}
fn load(&self) -> RegistryGenerationGuard {
RegistryGenerationGuard {
inner: self.current.load(),
}
}
fn publish(&self, generation: RegistryGeneration) {
self.current.store(Arc::new(generation));
}
}
struct RegistryGenerationGuard {
inner: registry_cell::RegistryCellGuard,
}
impl RegistryGenerationGuard {
fn slots_in_claim_order(&self) -> &[Arc<BlockSlot>] {
&self.inner.as_ref().slots_in_claim_order
}
fn classify_range(&self, start: usize, len: usize) -> Option<ClassifiedRange> {
self.inner.as_ref().classify_range(start, len)
}
}
struct RegistryGeneration {
slots_in_claim_order: Box<[Arc<BlockSlot>]>,
address_ranges: Box<[AddressRange]>,
}
impl RegistryGeneration {
fn empty() -> Self {
Self {
slots_in_claim_order: Box::default(),
address_ranges: Box::default(),
}
}
fn try_with_slot(slots: &[Arc<BlockSlot>], slot: &Arc<BlockSlot>) -> Result<Self, ArenaError> {
let new_len = slots
.len()
.checked_add(1)
.ok_or(ArenaError::RegistryCapacityOverflow)?;
let mut slots_in_claim_order = Vec::new();
slots_in_claim_order.try_reserve_exact(new_len)?;
slots_in_claim_order.extend(slots.iter().cloned());
slots_in_claim_order.push(Arc::clone(slot));
let mut address_ranges = Vec::new();
address_ranges.try_reserve_exact(new_len)?;
for (slot_index, slot) in slots_in_claim_order.iter().enumerate() {
address_ranges.push(AddressRange::for_slot(slot, slot_index)?);
}
address_ranges.sort_unstable_by_key(|range| range.start);
validate_address_ranges(&address_ranges)?;
Ok(Self {
slots_in_claim_order: slots_in_claim_order.into_boxed_slice(),
address_ranges: address_ranges.into_boxed_slice(),
})
}
fn classify_range(&self, start: usize, len: usize) -> Option<ClassifiedRange> {
if len == 0 {
return None;
}
let end = start.checked_add(len)?;
let candidate = self
.address_ranges
.partition_point(|range| range.start <= start)
.checked_sub(1)?;
let range = self.address_ranges.get(candidate)?;
if end > range.end {
return None;
}
let slot = Arc::clone(
self.slots_in_claim_order
.get(range.slot_index)
.unwrap_or_else(|| invariant_violation("registry range has an invalid slot index")),
);
Some(ClassifiedRange {
slot,
offset: start - range.start,
})
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct AddressRange {
start: usize,
end: usize,
slot_index: usize,
}
impl AddressRange {
fn for_slot(slot: &BlockSlot, slot_index: usize) -> Result<Self, ArenaError> {
let start = slot.base_address();
let len = slot.reserved_len();
let end = start.checked_add(len).ok_or(ArenaError::AddressOverflow {
slot_id: slot.id(),
start,
len,
})?;
Ok(Self {
start,
end,
slot_index,
})
}
#[cfg(test)]
fn new(start: usize, len: usize, slot_index: usize) -> Result<Self, ArenaError> {
let end = start.checked_add(len).ok_or(ArenaError::AddressOverflow {
slot_id: u32::MAX,
start,
len,
})?;
Ok(Self {
start,
end,
slot_index,
})
}
}
fn validate_address_ranges(ranges: &[AddressRange]) -> Result<(), ArenaError> {
for pair in ranges.windows(2) {
let first = pair[0];
let second = pair[1];
if first.end > second.start {
return Err(ArenaError::AddressOverlap {
first_start: first.start,
first_end: first.end,
second_start: second.start,
second_end: second.end,
});
}
}
Ok(())
}
pub(super) struct ClassifiedRange {
slot: Arc<BlockSlot>,
offset: usize,
}
impl ClassifiedRange {
pub(super) fn slot(&self) -> &Arc<BlockSlot> {
&self.slot
}
pub(super) fn offset(&self) -> usize {
self.offset
}
}
#[cfg(not(all(test, s3_tm_loom)))]
mod registry_cell {
use arc_swap::{ArcSwap, Guard};
use super::RegistryGeneration;
use crate::runtime::sync::sync::Arc;
pub(super) struct RegistryCell {
inner: ArcSwap<RegistryGeneration>,
}
impl RegistryCell {
pub(super) fn new(initial: Arc<RegistryGeneration>) -> Self {
Self {
inner: ArcSwap::from(initial),
}
}
pub(super) fn load(&self) -> RegistryCellGuard {
RegistryCellGuard {
inner: self.inner.load(),
}
}
pub(super) fn store(&self, generation: Arc<RegistryGeneration>) {
self.inner.store(generation);
}
}
pub(super) struct RegistryCellGuard {
inner: Guard<Arc<RegistryGeneration>>,
}
impl RegistryCellGuard {
pub(super) fn as_ref(&self) -> &RegistryGeneration {
&self.inner
}
}
}
#[cfg(all(test, s3_tm_loom))]
mod registry_cell {
use super::RegistryGeneration;
use crate::runtime::sync::sync::{Arc, Mutex};
pub(super) struct RegistryCell {
inner: Mutex<Arc<RegistryGeneration>>,
}
impl RegistryCell {
pub(super) fn new(initial: Arc<RegistryGeneration>) -> Self {
Self {
inner: Mutex::new(initial),
}
}
pub(super) fn load(&self) -> RegistryCellGuard {
RegistryCellGuard {
inner: Arc::clone(&self.inner.lock()),
}
}
pub(super) fn store(&self, generation: Arc<RegistryGeneration>) {
*self.inner.lock() = generation;
}
}
pub(super) struct RegistryCellGuard {
inner: Arc<RegistryGeneration>,
}
impl RegistryCellGuard {
pub(super) fn as_ref(&self) -> &RegistryGeneration {
&self.inner
}
}
}
#[cfg(all(test, not(s3_tm_loom)))]
mod tests {
use std::sync::Barrier;
use std::thread;
use super::super::admission::{AdmissionGuard, AdmissionState, MAX_PACKED_CARRIERS};
use super::super::block::TrimBlocked;
use super::super::test_util::operation_sequence::PLACEMENT_PROFILE;
use super::super::virtual_memory::{page_size, VirtualMemoryOperation};
use super::super::CarrierCount;
use super::*;
fn geometry() -> PoolGeometry {
geometry_with_carriers(4)
}
fn geometry_with_carriers(carriers: usize) -> PoolGeometry {
let page_size = page_size().unwrap().get();
PoolGeometry::new(
page_size,
page_size.checked_mul(carriers).unwrap(),
page_size,
)
.unwrap()
}
fn test_arena(
geometry: PoolGeometry,
optimistic_scan_words: usize,
) -> Result<Arena, ArenaError> {
Arena::new(geometry, ArenaOptions::new(optimistic_scan_words, true))
}
fn admission_with_prepared(prepared: CarrierCount) -> Mutex<AdmissionState> {
let state = Mutex::new(AdmissionState::new(MAX_PACKED_CARRIERS));
{
let mut admission = AdmissionGuard::new(state.lock());
*admission.prepared_capacity_mut() = prepared;
}
state
}
fn prepare_slots(arena: &Arena, count: usize) -> Vec<Arc<BlockSlot>> {
let mut prepared = CarrierCount::ZERO;
(0..count)
.map(|_| {
let slot = arena.reserve_slot().unwrap();
slot.prepare(&mut prepared).unwrap();
slot
})
.collect()
}
fn assert_fully_free(slot: &Arc<BlockSlot>) {
let all = BlockSlot::try_claim(slot, slot.carrier_count())
.unwrap()
.expect("every carrier should be free");
assert_eq!(all.len(), slot.carrier_count());
drop(all);
}
#[test]
fn empty_registry_classifies_no_range() {
let arena = test_arena(geometry(), 4).unwrap();
assert!(arena.classify_range(1, 1).is_none());
assert!(arena
.registry_generation()
.slots_in_claim_order()
.is_empty());
}
#[test]
fn slot_reservation_publishes_one_coherent_generation() {
let arena = test_arena(geometry(), 4).unwrap();
let first = arena.reserve_slot().unwrap();
let second = arena.reserve_slot().unwrap();
let generation = arena.registry_generation();
assert_eq!(
generation
.slots_in_claim_order()
.iter()
.map(|slot| slot.id())
.collect::<Vec<_>>(),
vec![0, 1]
);
assert_eq!(generation.inner.as_ref().address_ranges.len(), 2);
assert!(generation
.inner
.as_ref()
.address_ranges
.windows(2)
.all(|pair| pair[0].end <= pair[1].start));
assert!(generation
.slots_in_claim_order()
.iter()
.any(|slot| Arc::ptr_eq(slot, &first)));
assert!(generation
.slots_in_claim_order()
.iter()
.any(|slot| Arc::ptr_eq(slot, &second)));
}
#[test]
fn production_registry_guard_survives_concurrent_publication() {
let arena = Arc::new(test_arena(geometry(), 4).unwrap());
let first = arena.reserve_slot().unwrap();
let old_generation = arena.registry_generation();
let writer_arena = Arc::clone(&arena);
let writer = thread::spawn(move || writer_arena.reserve_slot().unwrap());
let second = writer.join().unwrap();
let new_generation = arena.registry_generation();
assert_eq!(old_generation.slots_in_claim_order().len(), 1);
assert!(Arc::ptr_eq(
&old_generation.slots_in_claim_order()[0],
&first
));
assert_eq!(new_generation.slots_in_claim_order().len(), 2);
assert!(new_generation
.slots_in_claim_order()
.iter()
.any(|slot| Arc::ptr_eq(slot, &first)));
assert!(new_generation
.slots_in_claim_order()
.iter()
.any(|slot| Arc::ptr_eq(slot, &second)));
}
#[test]
fn classification_requires_one_complete_nonempty_slot_range() {
let arena = test_arena(geometry(), 4).unwrap();
let slot = arena.reserve_slot().unwrap();
let range = slot.address_range().unwrap();
let complete = arena
.classify_range(range.start, range.len())
.expect("complete slot range is classified");
assert!(Arc::ptr_eq(complete.slot(), &slot));
assert_eq!(complete.offset(), 0);
let final_byte = arena
.classify_range(range.end - 1, 1)
.expect("final byte is inside the slot");
assert!(Arc::ptr_eq(final_byte.slot(), &slot));
assert_eq!(final_byte.offset(), range.len() - 1);
assert!(arena.classify_range(range.start, 0).is_none());
assert!(arena.classify_range(range.end - 1, 2).is_none());
assert!(arena.classify_range(usize::MAX, 2).is_none());
}
#[test]
fn classification_rejects_gaps_and_cross_slot_ranges() {
let geometry = geometry();
let slots_in_claim_order = (0..3)
.map(|slot_id| Arc::new(BlockSlot::new(slot_id, geometry).unwrap()))
.collect::<Vec<_>>()
.into_boxed_slice();
let generation = RegistryGeneration {
slots_in_claim_order,
address_ranges: vec![
AddressRange::new(0x1000, 0x1000, 0).unwrap(),
AddressRange::new(0x2000, 0x1000, 1).unwrap(),
AddressRange::new(0x4000, 0x1000, 2).unwrap(),
]
.into_boxed_slice(),
};
let second = generation
.classify_range(0x2000, 1)
.expect("the second range begins at its lower boundary");
assert!(Arc::ptr_eq(
second.slot(),
&generation.slots_in_claim_order[1]
));
assert_eq!(second.offset(), 0);
assert!(generation.classify_range(0x3000, 1).is_none());
assert!(generation.classify_range(0x1fff, 2).is_none());
}
#[test]
fn classification_survives_trimmed_block_backing() {
let arena = test_arena(geometry(), 4).unwrap();
let slot = arena.reserve_slot().unwrap();
let range = slot.address_range().unwrap();
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO)
.unwrap()
.finish()
.unwrap();
assert_eq!(prepared, CarrierCount::ZERO);
let classified = arena
.classify_range(range.start, range.len())
.expect("stable slot remains classified after trim");
assert!(Arc::ptr_eq(classified.slot(), &slot));
}
#[test]
fn address_validation_accepts_adjacency_and_rejects_overlap() {
let adjacent = [
AddressRange::new(0x1000, 0x1000, 0).unwrap(),
AddressRange::new(0x2000, 0x1000, 1).unwrap(),
];
assert!(validate_address_ranges(&adjacent).is_ok());
let overlap = [
AddressRange::new(0x1000, 0x1001, 0).unwrap(),
AddressRange::new(0x2000, 0x1000, 1).unwrap(),
];
assert!(matches!(
validate_address_ranges(&overlap),
Err(ArenaError::AddressOverlap { .. })
));
}
#[test]
fn synthetic_address_overflow_is_rejected() {
assert!(matches!(
AddressRange::new(usize::MAX, 2, 0),
Err(ArenaError::AddressOverflow { .. })
));
}
#[test]
fn exhausted_slot_ids_leave_the_registry_unchanged() {
let arena = test_arena(geometry(), 4).unwrap();
arena.state.lock().next_slot = None;
assert!(matches!(
arena.reserve_slot(),
Err(ArenaError::SlotIdExhausted)
));
assert!(arena
.registry_generation()
.slots_in_claim_order()
.is_empty());
}
#[test]
fn rejects_zero_scan_budget_and_zero_claim_count() {
assert!(matches!(
test_arena(geometry(), 0),
Err(ArenaError::InvalidScanBudget)
));
let arena = test_arena(geometry(), 1).unwrap();
assert!(matches!(
arena.claim_optimistic(CarrierCount::ZERO),
Err(ArenaError::InvalidClaimCount)
));
}
#[test]
fn empty_registry_returns_an_empty_partial_batch() {
let arena = test_arena(geometry(), 2).unwrap();
let batch = arena.claim_optimistic(CarrierCount::new(2)).unwrap();
assert_eq!(batch.required(), CarrierCount::new(2));
assert_eq!(batch.claimed(), CarrierCount::ZERO);
assert_eq!(batch.remaining(), CarrierCount::new(2));
assert_eq!(batch.inspected_words(), 0);
assert!(!batch.is_complete());
}
#[test]
fn incomplete_scan_charges_the_exact_budget() {
let arena = test_arena(geometry_with_carriers(130), 2).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let occupied = BlockSlot::try_claim(&slot, slot.carrier_count())
.unwrap()
.unwrap();
let batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::ZERO);
assert_eq!(batch.inspected_words(), 2);
drop(batch);
drop(occupied);
assert_fully_free(&slot);
}
#[test]
fn inactive_slots_consume_scan_positions() {
let arena = test_arena(geometry_with_carriers(1), 1).unwrap();
let inactive = arena.reserve_slot().unwrap();
let active = prepare_slots(&arena, 1).pop().unwrap();
let batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::ZERO);
assert_eq!(batch.inspected_words(), 1);
drop(batch);
assert_fully_free(&active);
assert!(BlockSlot::try_claim(&inactive, CarrierCount::new(1))
.unwrap()
.is_none());
}
#[test]
fn scan_origin_rotates_by_the_charged_budget() {
let arena = test_arena(geometry_with_carriers(130), 2).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let mut indices = Vec::new();
for _ in 0..3 {
let carriers = arena
.claim_optimistic(CarrierCount::new(1))
.unwrap()
.finish()
.unwrap();
indices.push(carriers[0].carrier_index());
drop(carriers);
}
assert_eq!(indices, vec![0, 128, 64]);
assert_fully_free(&slot);
}
#[test]
fn scan_origin_rotates_when_budget_covers_the_scan_space() {
let arena = test_arena(geometry_with_carriers(130), 3).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let mut indices = Vec::new();
for _ in 0..3 {
let carriers = arena
.claim_optimistic(CarrierCount::new(1))
.unwrap()
.finish()
.unwrap();
indices.push(carriers[0].carrier_index());
drop(carriers);
}
assert_eq!(indices, vec![0, 64, 128]);
assert_fully_free(&slot);
}
#[test]
fn placement_profile_matches_arena_whole_word_eligibility() {
let arena = test_arena(
geometry_with_carriers(PLACEMENT_PROFILE.block_carriers()),
1,
)
.unwrap();
for carriers in 0..=PLACEMENT_PROFILE.configured_carriers() + 1 {
assert_eq!(
arena
.contiguous_word_count(CarrierCount::new(carriers))
.is_some(),
PLACEMENT_PROFILE.is_whole_word_claim(carriers),
"placement profile drifted at {carriers} carriers"
);
}
}
#[test]
fn contiguous_scan_prefers_a_complete_run_over_fragmented_prefix() {
let arena = test_arena(geometry_with_carriers(192), 3).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let mut occupied = BlockSlot::try_claim(&slot, CarrierCount::new(192))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
drop(occupied.drain(64..192).collect::<Vec<_>>());
drop(occupied.drain(0..32).collect::<Vec<_>>());
let carriers = arena
.claim_optimistic(CarrierCount::new(128))
.unwrap()
.finish()
.unwrap();
assert_eq!(carriers.first().unwrap().carrier_index(), 64);
assert_eq!(carriers.last().unwrap().carrier_index(), 191);
drop(carriers);
drop(occupied);
assert_fully_free(&slot);
}
#[test]
fn whole_word_claim_larger_than_budget_skips_impossible_scan() {
const WORD_CARRIERS: usize = u64::BITS as usize;
let arena = test_arena(geometry_with_carriers(WORD_CARRIERS * 2), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let batch = arena
.claim_optimistic(CarrierCount::new(WORD_CARRIERS * 2))
.unwrap();
let diagnostics = arena.diagnostics();
let detailed = diagnostics
.detailed
.expect("test arena must collect detailed scan counters");
assert_eq!(batch.claimed(), CarrierCount::ZERO);
assert!(!batch.is_complete());
assert_eq!(detailed.optimistic_scans, 1);
assert_eq!(detailed.optimistic_scan_words, 0);
assert_eq!(diagnostics.optimistic_misses, 1);
drop(batch);
assert_fully_free(&slot);
}
#[test]
fn serialized_contiguous_scan_starts_from_the_rotating_cursor() {
let arena = test_arena(geometry_with_carriers(192), 1).unwrap();
let slots = prepare_slots(&arena, 2);
let mut occupied = BlockSlot::try_claim(&slots[0], CarrierCount::new(192))
.unwrap()
.unwrap()
.into_carriers()
.unwrap();
drop(occupied.drain(128..192).collect::<Vec<_>>());
drop(occupied.drain(0..64).collect::<Vec<_>>());
arena.scan_origin.store(2, Ordering::Relaxed);
let mut batch = arena.claim_optimistic(CarrierCount::new(128)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::ZERO);
let admission = admission_with_prepared(CarrierCount::new(384));
arena
.complete_claim_serialized(&mut AdmissionGuard::new(admission.lock()), &mut batch)
.unwrap();
let carriers = batch.finish().unwrap();
assert!(carriers
.iter()
.all(|carrier| carrier.slot_id() == slots[1].id()));
assert_eq!(carriers.first().unwrap().carrier_index(), 0);
assert_eq!(carriers.last().unwrap().carrier_index(), 127);
drop(carriers);
drop(occupied);
assert_fully_free(&slots[0]);
assert_fully_free(&slots[1]);
}
#[test]
fn contiguous_miss_preserves_fragmented_fallback() {
let arena = test_arena(geometry_with_carriers(192), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
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 mut batch = arena.claim_optimistic(CarrierCount::new(128)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::ZERO);
let admission = admission_with_prepared(CarrierCount::new(192));
arena
.complete_claim_serialized(&mut AdmissionGuard::new(admission.lock()), &mut batch)
.unwrap();
let carriers = batch.finish().unwrap();
assert_eq!(carriers.len(), 128);
assert_eq!(carriers.first().unwrap().carrier_index(), 0);
assert_eq!(carriers.last().unwrap().carrier_index(), 191);
drop(carriers);
drop(occupied);
assert_fully_free(&slot);
}
#[test]
fn scan_wraps_across_slot_and_bitmap_boundaries() {
let arena = test_arena(geometry_with_carriers(65), 3).unwrap();
let slots = prepare_slots(&arena, 2);
arena.scan_origin.store(3, Ordering::Relaxed);
let batch = arena.claim_optimistic(CarrierCount::new(66)).unwrap();
assert!(batch.is_complete());
assert_eq!(batch.inspected_words(), 3);
let carriers = batch.finish().unwrap();
assert_eq!(
(carriers[0].slot_id(), carriers[0].carrier_index()),
(slots[1].id(), 64)
);
assert!(carriers[1..]
.iter()
.all(|carrier| carrier.slot_id() == slots[0].id()));
assert_eq!(carriers[1].carrier_index(), 0);
assert_eq!(carriers.last().unwrap().carrier_index(), 64);
drop(carriers);
assert_fully_free(&slots[0]);
assert_fully_free(&slots[1]);
}
#[test]
fn one_batch_accumulates_carriers_across_blocks() {
let arena = test_arena(geometry_with_carriers(2), 2).unwrap();
let slots = prepare_slots(&arena, 2);
let batch = arena.claim_optimistic(CarrierCount::new(3)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::new(3));
assert_eq!(batch.inspected_words(), 2);
let carriers = batch.finish().unwrap();
assert_eq!(
carriers
.iter()
.filter(|carrier| carrier.slot_id() == slots[0].id())
.count(),
2
);
assert_eq!(
carriers
.iter()
.filter(|carrier| carrier.slot_id() == slots[1].id())
.count(),
1
);
drop(carriers);
assert_fully_free(&slots[0]);
assert_fully_free(&slots[1]);
}
#[test]
fn incomplete_finish_returns_all_provisional_bits() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let batch = arena.claim_optimistic(CarrierCount::new(3)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::new(2));
let error = match batch.finish() {
Ok(_) => panic!("an incomplete batch must not expose carriers"),
Err(error) => error,
};
assert!(matches!(
error,
ArenaError::IncompleteClaim {
required: 3,
claimed: 2
}
));
assert_fully_free(&slot);
}
#[test]
fn dropping_partial_batch_returns_all_provisional_bits() {
let arena = test_arena(geometry_with_carriers(65), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let batch = arena.claim_optimistic(CarrierCount::new(66)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::new(64));
drop(batch);
assert_fully_free(&slot);
}
#[test]
fn complete_batch_converts_exactly_the_requested_carriers() {
let arena = test_arena(geometry_with_carriers(70), 2).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let carriers = arena
.claim_optimistic(CarrierCount::new(67))
.unwrap()
.finish()
.unwrap();
assert_eq!(carriers.len(), 67);
assert_eq!(carriers.first().unwrap().carrier_index(), 0);
assert_eq!(carriers.last().unwrap().carrier_index(), 66);
drop(carriers);
assert_fully_free(&slot);
}
#[test]
fn concurrent_optimistic_claimants_cannot_share_a_carrier() {
let arena = Arc::new(test_arena(geometry_with_carriers(2), 1).unwrap());
let slot = prepare_slots(&arena, 1).pop().unwrap();
let start = Arc::new(Barrier::new(2));
let live = Arc::new(Barrier::new(2));
let claim = |arena: Arc<Arena>, start: Arc<Barrier>, live: Arc<Barrier>| {
thread::spawn(move || {
start.wait();
let carriers = loop {
let batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
if batch.is_complete() {
break batch.finish().unwrap();
}
thread::yield_now();
};
let id = (carriers[0].slot_id(), carriers[0].carrier_index());
live.wait();
drop(carriers);
id
})
};
let first = claim(Arc::clone(&arena), Arc::clone(&start), Arc::clone(&live));
let second = claim(Arc::clone(&arena), Arc::clone(&start), Arc::clone(&live));
assert_ne!(first.join().unwrap(), second.join().unwrap());
assert_fully_free(&slot);
}
#[test]
fn test_prepare_to_rounds_to_blocks_and_is_idempotent() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
arena
.prepare_to(&mut admission, CarrierCount::new(3))
.unwrap();
assert_eq!(admission.prepared_capacity(), CarrierCount::new(4));
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 2);
assert_eq!(arena.diagnostics().blocks_prepared, 2);
arena
.prepare_to(&mut admission, CarrierCount::new(4))
.unwrap();
assert_eq!(arena.diagnostics().blocks_prepared, 2);
}
#[test]
fn test_prepare_to_reuses_an_inactive_slot_before_reserving() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let slot = arena.reserve_slot().unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
arena
.prepare_to(&mut admission, CarrierCount::new(1))
.unwrap();
assert_eq!(admission.prepared_capacity(), CarrierCount::new(2));
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 1);
assert_fully_free(&slot);
}
#[test]
fn test_prepare_to_failure_retains_earlier_preparation() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let first = arena.reserve_slot().unwrap();
let second = arena.reserve_slot().unwrap();
second.inject_failure_once(VirtualMemoryOperation::Prepare);
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
let error = arena
.prepare_to(&mut admission, CarrierCount::new(3))
.unwrap_err();
assert!(matches!(
error,
ArenaError::Block(BlockError::VirtualMemory(ref error))
if error.operation() == VirtualMemoryOperation::Prepare
));
assert_eq!(admission.prepared_capacity(), CarrierCount::new(2));
assert_fully_free(&first);
assert!(BlockSlot::try_claim(&second, CarrierCount::new(1))
.unwrap()
.is_none());
arena
.prepare_to(&mut admission, CarrierCount::new(3))
.unwrap();
assert_eq!(admission.prepared_capacity(), CarrierCount::new(4));
assert_fully_free(&second);
}
#[test]
fn serialized_fallback_rechecks_active_capacity_before_growth() {
let arena = test_arena(geometry_with_carriers(65), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let occupied = BlockSlot::try_claim_words(&slot, 0, 1, CarrierCount::new(64))
.unwrap()
.into_provisional()
.unwrap();
let mut batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::ZERO);
let admission = admission_with_prepared(CarrierCount::new(65));
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
assert!(batch.is_complete());
assert_eq!(admission.prepared_capacity(), CarrierCount::new(65));
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 1);
let carriers = batch.finish().unwrap();
assert_eq!(carriers[0].carrier_index(), 64);
drop(carriers);
drop(occupied);
assert_fully_free(&slot);
}
#[test]
fn serialized_fallback_exhausts_fragmented_capacity_before_growth() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let slots = prepare_slots(&arena, 3);
let occupied = slots
.iter()
.map(|slot| {
BlockSlot::try_claim(slot, CarrierCount::new(1))
.unwrap()
.unwrap()
})
.collect::<Vec<_>>();
let mut batch = arena.claim_optimistic(CarrierCount::new(3)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::new(1));
let admission = admission_with_prepared(CarrierCount::new(6));
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
assert!(batch.is_complete());
assert_eq!(admission.prepared_capacity(), CarrierCount::new(6));
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 3);
let carriers = batch.finish().unwrap();
assert!(slots.iter().all(|slot| {
carriers
.iter()
.filter(|carrier| carrier.slot_id() == slot.id())
.count()
== 1
}));
drop(carriers);
drop(occupied);
for slot in &slots {
assert_fully_free(slot);
}
}
#[test]
fn serialized_fallback_reuses_inactive_slot_before_reserving() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let inactive = arena.reserve_slot().unwrap();
let mut batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
assert_eq!(admission.prepared_capacity(), CarrierCount::new(2));
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 1);
let carriers = batch.finish().unwrap();
assert_eq!(carriers[0].slot_id(), inactive.id());
drop(carriers);
assert_fully_free(&inactive);
}
#[test]
fn serialized_fallback_grows_whole_blocks_until_complete() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let mut batch = arena.claim_optimistic(CarrierCount::new(5)).unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
assert!(batch.is_complete());
assert_eq!(admission.prepared_capacity(), CarrierCount::new(6));
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 3);
let carriers = batch.finish().unwrap();
assert_eq!(carriers.len(), 5);
assert_eq!(
carriers
.iter()
.map(|carrier| carrier.slot_id())
.collect::<std::collections::BTreeSet<_>>()
.len(),
3
);
}
#[test]
fn later_preparation_failure_preserves_earlier_capacity() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let first = arena.reserve_slot().unwrap();
let second = arena.reserve_slot().unwrap();
second.inject_failure_once(VirtualMemoryOperation::Prepare);
let mut batch = arena.claim_optimistic(CarrierCount::new(3)).unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
let error = arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap_err();
assert!(matches!(
error,
ArenaError::Block(BlockError::VirtualMemory(ref error))
if error.operation() == VirtualMemoryOperation::Prepare
));
assert_eq!(admission.prepared_capacity(), CarrierCount::new(2));
assert_eq!(batch.claimed(), CarrierCount::new(2));
assert!(!batch.is_complete());
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 2);
drop(batch);
assert_fully_free(&first);
assert!(BlockSlot::try_claim(&second, CarrierCount::new(1))
.unwrap()
.is_none());
}
#[test]
fn serialized_growth_rejects_prepared_capacity_overflow() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let mut batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
let admission = admission_with_prepared(CarrierCount::new(usize::MAX));
let mut admission = AdmissionGuard::new(admission.lock());
let error = arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap_err();
assert!(matches!(
error,
ArenaError::Block(BlockError::PreparedCapacityOverflow)
));
assert_eq!(admission.prepared_capacity(), CarrierCount::new(usize::MAX));
assert_eq!(batch.claimed(), CarrierCount::ZERO);
let generation = arena.registry_generation();
assert_eq!(generation.slots_in_claim_order().len(), 1);
assert!(
BlockSlot::try_claim(&generation.slots_in_claim_order()[0], CarrierCount::new(1))
.unwrap()
.is_none()
);
}
#[test]
fn concurrent_serialized_fallbacks_retain_private_growth() {
let arena = Arc::new(test_arena(geometry_with_carriers(2), 1).unwrap());
let admission = Arc::new(admission_with_prepared(CarrierCount::ZERO));
let start = Arc::new(Barrier::new(2));
let fallback =
|arena: Arc<Arena>, admission: Arc<Mutex<AdmissionState>>, start: Arc<Barrier>| {
thread::spawn(move || {
let mut batch = arena.claim_optimistic(CarrierCount::new(2)).unwrap();
start.wait();
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
drop(admission);
batch.finish().unwrap()
})
};
let first = fallback(
Arc::clone(&arena),
Arc::clone(&admission),
Arc::clone(&start),
);
let second = fallback(
Arc::clone(&arena),
Arc::clone(&admission),
Arc::clone(&start),
);
let first = first.join().unwrap();
let second = second.join().unwrap();
assert_eq!(
AdmissionGuard::new(admission.lock()).prepared_capacity(),
CarrierCount::new(4)
);
assert_eq!(arena.registry_generation().slots_in_claim_order().len(), 2);
assert!(first.iter().all(|left| second.iter().all(|right| {
(left.slot_id(), left.carrier_index()) != (right.slot_id(), right.carrier_index())
})));
}
#[test]
fn trim_selection_skips_inactive_and_occupied_slots() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let inactive = arena.reserve_slot().unwrap();
let active = prepare_slots(&arena, 2);
let occupied = BlockSlot::try_claim(&active[0], CarrierCount::new(1))
.unwrap()
.unwrap();
let candidate = arena
.select_trim_candidate()
.expect("one active block is free");
assert!(Arc::ptr_eq(&candidate, &active[1]));
assert!(!Arc::ptr_eq(&candidate, &inactive));
assert_eq!(arena.diagnostics().trim_slots_scanned, 3);
drop(occupied);
}
#[test]
fn trim_candidate_is_rechecked_after_selection() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let candidate = arena
.select_trim_candidate()
.expect("prepared block is initially free");
let occupied = BlockSlot::try_claim(&slot, CarrierCount::new(1))
.unwrap()
.unwrap();
let mut prepared = CarrierCount::new(2);
assert!(matches!(
BlockSlot::start_trim(&candidate, &mut prepared, CarrierCount::ZERO),
Err(TrimBlocked::Busy)
));
assert_eq!(prepared, CarrierCount::new(2));
drop(occupied);
}
#[test]
fn trim_selection_skips_cleanup_owned_slot() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let mut prepared = CarrierCount::new(2);
let cleanup = BlockSlot::start_trim(&slot, &mut prepared, CarrierCount::ZERO).unwrap();
assert!(arena.select_trim_candidate().is_none());
assert_eq!(arena.diagnostics().trim_slots_scanned, 1);
cleanup.finish().unwrap();
}
#[test]
fn arena_diagnostics_record_scan_growth_and_rollback() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
arena.reserve_slot().unwrap();
let mut batch = arena.claim_optimistic(CarrierCount::new(3)).unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
let before_rollback = arena.diagnostics();
let detailed = before_rollback
.detailed
.expect("test arena must collect detailed scan counters");
assert_eq!(detailed.optimistic_scans, 1);
assert_eq!(detailed.optimistic_scan_words, 1);
assert_eq!(before_rollback.optimistic_misses, 1);
assert_eq!(before_rollback.serialized_fallbacks, 1);
assert_eq!(before_rollback.serialized_slots_inspected, 2);
assert_eq!(before_rollback.blocks_prepared, 2);
assert_eq!(before_rollback.block_ranges_reserved, 2);
assert_eq!(before_rollback.rolled_back_carriers, 0);
drop(batch);
assert_eq!(arena.diagnostics().rolled_back_carriers, 3);
}
#[test]
fn serialized_completion_is_a_noop_for_an_already_complete_batch() {
let arena = test_arena(geometry_with_carriers(1), 1).unwrap();
prepare_slots(&arena, 1);
let mut batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
assert!(batch.is_complete());
let admission = admission_with_prepared(CarrierCount::new(1));
let mut admission = AdmissionGuard::new(admission.lock());
let before = arena.diagnostics();
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
assert_eq!(
arena.diagnostics().serialized_fallbacks,
before.serialized_fallbacks
);
drop(batch);
}
fn assert_packed_fallback_work(
block_counts: &[usize],
carriers_per_block: usize,
optimistic_scan_words: usize,
iterations: u64,
) {
for &blocks in block_counts {
let full_blocks = blocks * 7 / 8;
let arena = test_arena(
geometry_with_carriers(carriers_per_block),
optimistic_scan_words,
)
.unwrap();
let slots = prepare_slots(&arena, blocks);
let occupied = slots
.iter()
.take(full_blocks)
.map(|slot| {
BlockSlot::try_claim(slot, slot.carrier_count())
.unwrap()
.expect("packed block should be free")
})
.collect::<Vec<_>>();
let prepared = CarrierCount::new(blocks * carriers_per_block);
let admission = admission_with_prepared(prepared);
let before = arena.diagnostics();
for _ in 0..iterations {
let mut batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
if !batch.is_complete() {
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
}
drop(batch);
}
let after = arena.diagnostics();
let fallbacks = after.serialized_fallbacks - before.serialized_fallbacks;
let before_detailed = before
.detailed
.expect("test arena must collect detailed scan counters");
let after_detailed = after
.detailed
.expect("test arena must collect detailed scan counters");
let optimistic_scans =
after_detailed.optimistic_scans - before_detailed.optimistic_scans;
let recorded_slots =
after.serialized_slots_inspected - before.serialized_slots_inspected;
let expected_fallbacks = iterations * 7 / 8;
let expected_slots = usize::try_from(expected_fallbacks)
.unwrap()
.checked_mul(full_blocks + 1)
.unwrap();
eprintln!(
"blocks={blocks} full_blocks={full_blocks} \
iterations={iterations} fallbacks={fallbacks} \
serialized_slots_inspected={recorded_slots}"
);
assert_eq!(optimistic_scans, iterations);
assert_eq!(fallbacks, expected_fallbacks);
assert_eq!(recorded_slots, expected_slots as u64);
drop(occupied);
}
}
#[test]
#[cfg_attr(
miri,
ignore = "registry-size work counting is covered by native suites; focused Miri tests cover allocator pointer safety"
)]
fn packed_fallback_work_has_an_exact_ci_regression_barrier() {
assert_packed_fallback_work(&[8, 16, 32, 64, 128, 256], 64, 1, 256);
}
#[test]
fn whole_word_miss_has_an_exact_serialized_work_barrier() {
const SLOTS: usize = 4;
const WORDS_PER_SLOT: usize = 2;
const REQUEST: usize = WORDS_PER_SLOT * u64::BITS as usize;
let arena = test_arena(geometry_with_carriers(REQUEST), WORDS_PER_SLOT).unwrap();
let slots = prepare_slots(&arena, SLOTS);
let mut blockers = Vec::new();
for slot in &slots {
for word in 0..WORDS_PER_SLOT {
let blocker = BlockSlot::try_claim_words(slot, word, 1, CarrierCount::new(1))
.unwrap()
.into_provisional()
.expect("one carrier remains free in each word")
.into_carriers()
.unwrap();
blockers.push(blocker);
}
}
let admission = admission_with_prepared(CarrierCount::new(SLOTS * REQUEST));
let before = arena.diagnostics();
let mut batch = arena.claim_optimistic(CarrierCount::new(REQUEST)).unwrap();
assert_eq!(batch.claimed(), CarrierCount::ZERO);
arena
.complete_claim_serialized(&mut AdmissionGuard::new(admission.lock()), &mut batch)
.unwrap();
let carriers = batch.finish().unwrap();
let after = arena.diagnostics();
assert_eq!(after.serialized_fallbacks - before.serialized_fallbacks, 1);
assert_eq!(
after.serialized_slots_inspected - before.serialized_slots_inspected,
6
);
assert_eq!(after.blocks_prepared, before.blocks_prepared);
assert_eq!(after.block_ranges_reserved, before.block_ranges_reserved);
assert_eq!(
carriers
.iter()
.filter(|carrier| carrier.slot_id() == slots[0].id())
.count(),
REQUEST - WORDS_PER_SLOT
);
assert_eq!(
carriers
.iter()
.filter(|carrier| carrier.slot_id() == slots[1].id())
.count(),
WORDS_PER_SLOT
);
drop(carriers);
drop(blockers);
for slot in &slots {
assert_fully_free(slot);
}
}
#[test]
#[ignore = "manual allocator work probe"]
fn test_packed_fallback_work_scales_with_registry() {
assert_packed_fallback_work(&[8, 16, 32, 64, 128, 256], 8_192, 32, 8_192);
}
#[test]
fn completed_batch_is_not_recorded_as_rollback() {
let arena = test_arena(geometry_with_carriers(2), 1).unwrap();
let slot = prepare_slots(&arena, 1).pop().unwrap();
let carriers = arena
.claim_optimistic(CarrierCount::new(1))
.unwrap()
.finish()
.unwrap();
assert_eq!(arena.diagnostics().rolled_back_carriers, 0);
drop(carriers);
assert_eq!(arena.diagnostics().rolled_back_carriers, 0);
assert_fully_free(&slot);
}
#[test]
fn arena_diagnostics_saturate() {
let diagnostics = ArenaDiagnostics::new(true);
diagnostics
.rolled_back_carriers
.store(u64::MAX - 1, DiagnosticOrdering::Relaxed);
diagnostics.record_rolled_back_carriers(usize::MAX);
diagnostics.record_rolled_back_carriers(1);
assert_eq!(diagnostics.snapshot().rolled_back_carriers, u64::MAX);
}
#[test]
fn basic_diagnostics_omit_success_path_scan_counters() {
let arena = Arena::new(geometry_with_carriers(2), ArenaOptions::new(1, false)).unwrap();
let mut batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
let diagnostics = arena.diagnostics();
assert_eq!(diagnostics.optimistic_misses, 1);
assert_eq!(diagnostics.serialized_fallbacks, 1);
assert_eq!(diagnostics.serialized_slots_inspected, 0);
assert_eq!(diagnostics.detailed, None);
}
#[test]
fn wrapped_scan_position_does_not_overflow() {
assert_eq!(wrapped_position(3, 0, 4), 3);
assert_eq!(wrapped_position(3, 1, 4), 0);
assert_eq!(wrapped_position(3, 3, 4), 2);
assert_eq!(wrapped_position(usize::MAX - 1, 1, usize::MAX), 0);
}
}
#[cfg(all(test, s3_tm_loom))]
mod loom_tests {
use super::super::admission::{AdmissionGuard, AdmissionState, MAX_PACKED_CARRIERS};
use super::super::virtual_memory::page_size;
use super::*;
use crate::runtime::sync::thread;
fn test_arena(
geometry: PoolGeometry,
optimistic_scan_words: usize,
) -> Result<Arena, ArenaError> {
Arena::new(geometry, ArenaOptions::new(optimistic_scan_words, true))
}
fn admission_with_prepared(prepared: CarrierCount) -> Mutex<AdmissionState> {
let state = Mutex::new(AdmissionState::new(MAX_PACKED_CARRIERS));
{
let mut admission = AdmissionGuard::new(state.lock());
*admission.prepared_capacity_mut() = prepared;
}
state
}
fn assert_coherent(generation: &RegistryGenerationGuard) {
let generation = generation.inner.as_ref();
assert_eq!(
generation.slots_in_claim_order.len(),
generation.address_ranges.len()
);
for range in &generation.address_ranges {
let slot = &generation.slots_in_claim_order[range.slot_index];
assert_eq!(slot.address_range(), Some(range.start..range.end));
}
}
#[test]
fn registry_generation_is_published_coherently() {
loom::model(|| {
let page_size = page_size().unwrap().get();
let geometry = PoolGeometry::new(page_size, page_size, page_size).unwrap();
let arena = Arc::new(test_arena(geometry, 1).unwrap());
arena.reserve_slot().unwrap();
let writer_arena = Arc::clone(&arena);
let writer = thread::spawn(move || {
writer_arena.reserve_slot().unwrap();
});
let reader_arena = Arc::clone(&arena);
let reader = thread::spawn(move || {
assert_coherent(&reader_arena.registry_generation());
});
writer.join().unwrap();
reader.join().unwrap();
let generation = arena.registry_generation();
assert_coherent(&generation);
assert_eq!(generation.slots_in_claim_order().len(), 2);
});
}
#[test]
fn completed_concurrent_batches_cannot_own_the_same_carrier() {
loom::model(|| {
let page_size = page_size().unwrap().get();
let geometry = PoolGeometry::new(page_size, page_size * 2, page_size).unwrap();
let arena = Arc::new(test_arena(geometry, 1).unwrap());
let slot = arena.reserve_slot().unwrap();
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
let claim = |arena: Arc<Arena>| {
thread::spawn(move || {
let batch = arena.claim_optimistic(CarrierCount::new(1)).unwrap();
if batch.is_complete() {
Some(batch.finish().unwrap())
} else {
None
}
})
};
let first = claim(Arc::clone(&arena));
let second = claim(Arc::clone(&arena));
let first = first.join().unwrap();
let second = second.join().unwrap();
assert!(first.is_some() || second.is_some());
if let (Some(first), Some(second)) = (&first, &second) {
assert_ne!(first[0].carrier_index(), second[0].carrier_index());
}
});
}
#[test]
fn concurrent_claims_use_distinct_rotated_windows() {
loom::model(|| {
let page_size = page_size().unwrap().get();
let geometry = PoolGeometry::new(page_size, page_size * 65, page_size).unwrap();
let arena = Arc::new(test_arena(geometry, 1).unwrap());
let slot = arena.reserve_slot().unwrap();
let mut prepared = CarrierCount::ZERO;
slot.prepare(&mut prepared).unwrap();
let claim = |arena: Arc<Arena>| {
thread::spawn(move || {
arena
.claim_optimistic(CarrierCount::new(1))
.unwrap()
.finish()
.unwrap()
})
};
let first = claim(Arc::clone(&arena));
let second = claim(Arc::clone(&arena));
let first = first.join().unwrap();
let second = second.join().unwrap();
let mut indices = [first[0].carrier_index(), second[0].carrier_index()];
indices.sort_unstable();
assert_eq!(indices, [0, 64]);
drop(first);
drop(second);
let returned = BlockSlot::try_claim(&slot, slot.carrier_count())
.unwrap()
.expect("both rotated-window owners returned");
assert_eq!(returned.len(), slot.carrier_count());
});
}
#[test]
fn private_growth_cannot_be_stolen_by_an_optimistic_claim() {
loom::model(|| {
let page_size = page_size().unwrap().get();
let geometry = PoolGeometry::new(page_size, page_size * 2, page_size).unwrap();
let arena = Arc::new(test_arena(geometry, 1).unwrap());
let fallback_arena = Arc::clone(&arena);
let fallback = thread::spawn(move || {
let mut batch = fallback_arena
.claim_optimistic(CarrierCount::new(1))
.unwrap();
let admission = admission_with_prepared(CarrierCount::ZERO);
let mut admission = AdmissionGuard::new(admission.lock());
fallback_arena
.complete_claim_serialized(&mut admission, &mut batch)
.unwrap();
assert_eq!(admission.prepared_capacity(), CarrierCount::new(2));
batch.finish().unwrap()
});
let optimistic_arena = Arc::clone(&arena);
let optimistic = thread::spawn(move || {
let batch = optimistic_arena
.claim_optimistic(CarrierCount::new(1))
.unwrap();
if batch.is_complete() {
Some(batch.finish().unwrap())
} else {
None
}
});
let fallback = fallback.join().unwrap();
let optimistic = optimistic.join().unwrap();
assert_eq!(fallback.len(), 1);
if let Some(optimistic) = optimistic {
assert_ne!(
(fallback[0].slot_id(), fallback[0].carrier_index()),
(optimistic[0].slot_id(), optimistic[0].carrier_index())
);
}
});
}
}