use std::alloc::Layout;
use std::cell::{Cell, RefCell};
use std::collections::HashMap;
use std::mem::size_of;
use std::ptr::NonNull;
use std::sync::atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering};
use std::sync::{Arc, RwLock, Weak};
use crossbeam_epoch::{Atomic, Collector, LocalHandle, Owned, Shared};
use crate::config::{
Config, MAX_BLACK_SPAN_RING_CAPACITY, MAX_LOCAL_MAGAZINE_CAPACITY,
MAX_LOW_CAPACITY_PAGE_QUEUE_SPANS, MAX_RECENT_SPANS_PER_CLASS, MAX_REMOTE_CACHE_CAPACITY,
SIZE_CLASSES, SMALL_SPAN_SIZE, TrimMode, headerless_small_class_for_size, small_payload_offset,
small_span_capacity,
};
use crate::os::{BackingStore, PlatformBacking};
use crate::span::{ANCHOR_MAGIC, RUN_MAGIC, RunHeader, SpanAnchor, SpanDesc, SpanHandle, SpanKind};
use crate::stats::{AtomicStats, StatsSnapshot, TrimStats};
use crate::topology::{ChunkRecord, LocalityHint, Topology, TopologyReadSnapshot, align_up};
use crate::{BoAllocError, InvariantError};
static NEXT_ALLOCATOR_ID: AtomicU64 = AtomicU64::new(1);
static NEXT_OWNER_TOKEN: AtomicU64 = AtomicU64::new(1);
const RECENT_SPANS_PER_CLASS: usize = MAX_RECENT_SPANS_PER_CLASS;
const INITIAL_RUN_TERRITORY_EXTENTS: usize = 8;
const RECENT_RUNS: usize =
INITIAL_RUN_TERRITORY_EXTENTS + crate::config::MAX_ADAPTIVE_RUN_TERRITORY_EXTENSION_EXTENTS;
const RECENT_DEDICATED_RUNS: usize = 8;
const RUN_LOCAL_WINDOWS: usize = 4;
const INITIAL_RUN_LOCAL_WINDOW_TARGET: u32 = 2;
const TERRITORY_CACHE_FIRST_CLASS: usize = 22;
const TERRITORY_CACHE_CLASSES: usize = SIZE_CLASSES.len() - TERRITORY_CACHE_FIRST_CLASS;
const MAINTENANCE_BIT: usize = 1 << (usize::BITS - 1);
#[derive(Clone)]
struct CachedSpan {
span: SpanHandle,
generation: u64,
}
impl CachedSpan {
fn pointer(&self) -> *const SpanDesc {
self.span.as_ptr()
}
}
struct CachedClass {
recent: [Option<CachedSpan>; RECENT_SPANS_PER_CLASS],
territory_return: Option<CachedSpan>,
magazine: LocalMagazine,
black_ring: BlackSpanRing,
remote: RemoteMagazine,
cohort_epoch: u64,
}
struct TerritoryCache {
spans: [Option<CachedSpan>; MAX_LOW_CAPACITY_PAGE_QUEUE_SPANS],
len: usize,
cursor: usize,
}
impl Default for TerritoryCache {
fn default() -> Self {
Self {
spans: std::array::from_fn(|_| None),
len: 0,
cursor: 0,
}
}
}
impl TerritoryCache {
#[inline]
fn get_by_base(&self, base: usize) -> Option<&CachedSpan> {
let first = self.spans.first()?.as_ref()?;
let offset = base.checked_sub(first.span.base)?;
if offset % SMALL_SPAN_SIZE != 0 {
return None;
}
let index = offset / SMALL_SPAN_SIZE;
(index < self.len)
.then(|| self.spans[index].as_ref())
.flatten()
.filter(|cached| cached.span.base == base)
}
}
struct LocalMagazine {
pointer: *const SpanDesc,
generation: u64,
entries: [usize; MAX_LOCAL_MAGAZINE_CAPACITY],
len: usize,
leased: bool,
target: usize,
live_delta: i32,
requested_delta: i64,
overflow_head: usize,
overflow_len: u32,
}
impl LocalMagazine {
fn clear(&mut self) {
debug_assert_eq!(self.overflow_head, 0);
debug_assert_eq!(self.overflow_len, 0);
self.pointer = std::ptr::null();
self.generation = 0;
self.len = 0;
self.leased = false;
self.live_delta = 0;
self.requested_delta = 0;
self.overflow_head = 0;
self.overflow_len = 0;
}
#[inline]
fn grow_after_drain(&mut self, maximum: usize) {
self.target = self.target.max(1).saturating_mul(2).min(maximum);
}
#[inline]
fn push(&mut self, pointer: *const SpanDesc, generation: u64, entry: usize, limit: usize) {
if limit == 0 {
return;
}
if self.pointer != pointer || self.generation != generation {
assert!(
!self.leased,
"a live magazine must be flushed before changing spans"
);
self.clear();
self.pointer = pointer;
self.generation = generation;
self.leased = true;
}
debug_assert!(self.len < limit);
self.entries[self.len] = entry;
self.len += 1;
}
#[inline]
fn push_leased(&mut self, entry: usize, limit: usize) {
debug_assert!(self.leased);
debug_assert!(!self.pointer.is_null());
debug_assert_ne!(limit, 0);
debug_assert!(self.len < limit);
self.entries[self.len] = entry;
self.len += 1;
}
#[inline]
fn pop(&mut self) -> Option<(*const SpanDesc, u64, usize)> {
if self.len == 0 {
return None;
}
self.len -= 1;
Some((self.pointer, self.generation, self.entries[self.len]))
}
#[inline]
fn record_allocation(&mut self, layout: Layout) {
self.live_delta += 1;
self.requested_delta += layout.size() as i64;
}
#[inline]
fn record_deallocation(&mut self, layout: Layout) {
self.live_delta -= 1;
self.requested_delta -= layout.size() as i64;
}
#[inline]
fn fold_accounting(&mut self, span: &SpanDesc) {
span.synchronize_local_cache_accounting(self.live_delta, self.requested_delta);
self.live_delta = 0;
self.requested_delta = 0;
}
fn detach_exhausted_lease(&mut self, span: &SpanDesc) -> BlackSpanLease {
debug_assert!(self.leased);
debug_assert!(std::ptr::eq(self.pointer, span));
debug_assert_eq!(self.len, 0);
debug_assert_eq!(self.overflow_head, 0);
debug_assert_eq!(self.overflow_len, 0);
debug_assert_eq!(self.live_delta, 0);
debug_assert_eq!(self.requested_delta, 0);
let entry = BlackSpanLease {
pointer: self.pointer,
base: span.base,
generation: self.generation,
..BlackSpanLease::default()
};
self.pointer = std::ptr::null();
self.generation = 0;
self.leased = false;
entry
}
unsafe fn push_overflow(&mut self, address: usize) {
debug_assert!(self.leased);
debug_assert_ne!(address, 0);
debug_assert_eq!(address % std::mem::align_of::<usize>(), 0);
unsafe { (address as *mut usize).write(self.overflow_head) };
self.overflow_head = address;
self.overflow_len += 1;
}
unsafe fn pop_overflow(&mut self) -> Option<usize> {
let address = self.overflow_head;
if address == 0 {
return None;
}
self.overflow_head = unsafe { (address as *const usize).read() };
self.overflow_len -= 1;
Some(address)
}
fn flush(&mut self, recent_free_word_hints: usize) {
if !self.leased {
self.clear();
return;
}
let span = unsafe { &*self.pointer };
for address in self.entries[..self.len].iter().copied() {
span.publish_local_cached_address(address, recent_free_word_hints);
}
while self.overflow_head != 0 {
let address = unsafe {
self.pop_overflow()
.expect("a non-empty overflow chain has a head")
};
span.publish_local_cached_address(address, recent_free_word_hints);
}
self.fold_accounting(span);
span.release_local_cache_lease();
self.clear();
self.target = 0;
}
}
#[derive(Clone, Copy)]
struct BlackSpanLease {
pointer: *const SpanDesc,
base: usize,
generation: u64,
free_head: usize,
free_len: u32,
live_delta: i32,
requested_delta: i64,
}
impl Default for BlackSpanLease {
fn default() -> Self {
Self {
pointer: std::ptr::null(),
base: 0,
generation: 0,
free_head: 0,
free_len: 0,
live_delta: 0,
requested_delta: 0,
}
}
}
impl BlackSpanLease {
#[inline]
unsafe fn push(&mut self, address: usize, layout: Layout) {
debug_assert!(!self.pointer.is_null());
debug_assert_ne!(address, 0);
debug_assert_eq!(address % std::mem::align_of::<usize>(), 0);
unsafe { (address as *mut usize).write(self.free_head) };
self.free_head = address;
self.free_len += 1;
self.live_delta -= 1;
self.requested_delta -= layout.size() as i64;
}
#[inline]
unsafe fn pop_address(&mut self) -> Option<usize> {
let address = self.free_head;
if address == 0 {
return None;
}
self.free_head = unsafe { (address as *const usize).read() };
self.free_len -= 1;
Some(address)
}
#[inline]
unsafe fn pop(&mut self, layout: Layout) -> Option<usize> {
let address = unsafe { self.pop_address() }?;
self.live_delta += 1;
self.requested_delta += layout.size() as i64;
Some(address)
}
fn fold_accounting(&mut self, span: &SpanDesc) {
span.synchronize_local_cache_accounting(self.live_delta, self.requested_delta);
self.live_delta = 0;
self.requested_delta = 0;
}
fn flush(&mut self, recent_free_word_hints: usize) {
if self.pointer.is_null() {
*self = Self::default();
return;
}
let span = unsafe { &*self.pointer };
while self.free_head != 0 {
let address = unsafe {
self.pop_address()
.expect("a non-empty Black ring chain has a head")
};
span.publish_local_cached_address(address, recent_free_word_hints);
}
self.fold_accounting(span);
span.release_local_cache_lease();
*self = Self::default();
}
}
struct BlackSpanRing {
entries: [BlackSpanLease; MAX_BLACK_SPAN_RING_CAPACITY],
len: usize,
}
impl Default for BlackSpanRing {
fn default() -> Self {
Self {
entries: [BlackSpanLease::default(); MAX_BLACK_SPAN_RING_CAPACITY],
len: 0,
}
}
}
impl BlackSpanRing {
fn retain(&mut self, entry: BlackSpanLease, limit: usize, recent_free_word_hints: usize) {
debug_assert!(!entry.pointer.is_null());
debug_assert!(limit <= MAX_BLACK_SPAN_RING_CAPACITY);
if limit == 0 {
let mut entry = entry;
entry.flush(recent_free_word_hints);
return;
}
if self.len == limit {
self.entries[self.len - 1].flush(recent_free_word_hints);
self.len -= 1;
}
self.entries.copy_within(0..self.len, 1);
self.entries[0] = entry;
self.len += 1;
}
#[inline]
fn find_by_base_mut(&mut self, base: usize) -> Option<&mut BlackSpanLease> {
self.entries[..self.len]
.iter_mut()
.find(|entry| entry.base == base)
}
fn take_by_pointer(
&mut self,
pointer: *const SpanDesc,
generation: u64,
) -> Option<BlackSpanLease> {
let index = self.entries[..self.len]
.iter()
.position(|entry| entry.pointer == pointer && entry.generation == generation)?;
let entry = self.entries[index];
self.entries.copy_within(index + 1..self.len, index);
self.len -= 1;
self.entries[self.len] = BlackSpanLease::default();
Some(entry)
}
#[inline]
unsafe fn pop(&mut self, layout: Layout) -> Option<(*const SpanDesc, u64, usize)> {
for entry in &mut self.entries[..self.len] {
if entry.free_head == 0 {
continue;
}
let pointer = entry.pointer;
let generation = entry.generation;
let address = unsafe { entry.pop(layout) }?;
return Some((pointer, generation, address));
}
None
}
fn fold_accounting(&mut self) {
for entry in &mut self.entries[..self.len] {
let span = unsafe { &*entry.pointer };
entry.fold_accounting(span);
}
}
fn flush(&mut self, recent_free_word_hints: usize) {
for entry in &mut self.entries[..self.len] {
entry.flush(recent_free_word_hints);
}
self.len = 0;
}
}
struct RemoteMagazine {
pointer: *const SpanDesc,
entries: [usize; MAX_REMOTE_CACHE_CAPACITY],
requested: [u16; MAX_REMOTE_CACHE_CAPACITY],
len: usize,
target: usize,
}
impl RemoteMagazine {
fn pop(&mut self, layout: Layout) -> Option<usize> {
let requested = u16::try_from(layout.size()).ok()?;
let index = self.requested[..self.len]
.iter()
.rposition(|candidate| *candidate == requested)?;
self.len -= 1;
let address = self.entries[index];
self.entries[index] = self.entries[self.len];
self.requested[index] = self.requested[self.len];
if self.len == 0 {
self.pointer = std::ptr::null();
}
Some(address)
}
unsafe fn push(
&mut self,
span: &SpanDesc,
address: usize,
layout: Layout,
class_index: usize,
limit: usize,
) -> usize {
let mut published = 0;
let pointer = span as *const SpanDesc;
if self.pointer != pointer && self.len != 0 {
published += unsafe { self.flush(class_index) };
}
self.pointer = pointer;
self.entries[self.len] = address;
self.requested[self.len] = layout.size() as u16;
self.len += 1;
self.target = self.target.max(1).min(limit);
if self.len == self.target {
if self.target < limit {
self.target = self.target.saturating_mul(2).min(limit);
} else {
published += unsafe { self.flush(class_index) };
}
}
published
}
unsafe fn flush(&mut self, class_index: usize) -> usize {
if self.len == 0 {
self.pointer = std::ptr::null();
return 0;
}
let span = unsafe { &*self.pointer };
unsafe {
span.publish_remote_cached_batch(
&self.entries[..self.len],
&self.requested[..self.len],
class_index,
)
};
let published = self.len;
self.len = 0;
self.pointer = std::ptr::null();
published
}
}
#[derive(Clone, Copy, Eq, PartialEq)]
enum SnapshotSearchScope {
Local,
Global,
}
#[inline]
fn territory_cache_index(class_index: usize) -> Option<usize> {
(class_index >= TERRITORY_CACHE_FIRST_CLASS && small_span_capacity(class_index) <= 2)
.then(|| class_index - TERRITORY_CACHE_FIRST_CLASS)
}
#[inline]
fn visit_locality_window<T, R>(
items: &[T],
hint: LocalityHint,
max_candidates: usize,
address_of: impl Fn(&T) -> usize + Copy,
chunk_of: impl Fn(&T) -> usize + Copy,
mut visit: impl FnMut(&T) -> Option<R>,
) -> Option<R> {
if items.is_empty() || max_candidates == 0 {
return None;
}
let insertion = items.partition_point(|item| address_of(item) < hint.address);
let window = max_candidates.min(items.len());
let start = insertion
.saturating_sub(window / 2)
.min(items.len() - window);
let end = start + window;
let center = insertion.clamp(start, end);
for prefer_same_chunk in [true, false] {
let mut left = center;
let mut right = center;
while left > start || right < end {
let take_right = if left == start {
true
} else if right == end {
false
} else {
address_of(&items[right]).abs_diff(hint.address)
<= address_of(&items[left - 1]).abs_diff(hint.address)
};
let index = if take_right {
let index = right;
right += 1;
index
} else {
left -= 1;
left
};
let item = &items[index];
if (chunk_of(item) == hint.chunk_base) != prefer_same_chunk {
continue;
}
if let Some(result) = visit(item) {
return Some(result);
}
}
}
None
}
impl Default for CachedClass {
fn default() -> Self {
Self {
recent: std::array::from_fn(|_| None),
territory_return: None,
magazine: LocalMagazine {
pointer: std::ptr::null(),
generation: 0,
entries: [0; MAX_LOCAL_MAGAZINE_CAPACITY],
len: 0,
leased: false,
target: 0,
live_delta: 0,
requested_delta: 0,
overflow_head: 0,
overflow_len: 0,
},
black_ring: BlackSpanRing::default(),
remote: RemoteMagazine {
pointer: std::ptr::null(),
entries: [0; MAX_REMOTE_CACHE_CAPACITY],
requested: [0; MAX_REMOTE_CACHE_CAPACITY],
len: 0,
target: 1,
},
cohort_epoch: 0,
}
}
}
struct LocalCache {
#[cfg(debug_assertions)]
active: Cell<bool>,
inner: Weak<Inner>,
epoch_handle: LocalHandle,
owner: u64,
trim_epoch: u64,
rng: u64,
classes: [CachedClass; SIZE_CLASSES.len()],
low_capacity_territories: [TerritoryCache; TERRITORY_CACHE_CLASSES],
runs: [Option<CachedSpan>; RECENT_RUNS],
dedicated_runs: [Option<CachedSpan>; RECENT_DEDICATED_RUNS],
run_windows: [RunLocalWindow; RUN_LOCAL_WINDOWS],
run_len: usize,
dedicated_run_len: usize,
run_cursor: usize,
dedicated_run_cursor: usize,
run_window_cursor: usize,
}
struct RunLocalWindow {
cached: Option<CachedSpan>,
extent_size: usize,
next: u32,
end: u32,
target: u32,
}
struct PreparedRun {
user: usize,
usable: usize,
activated: bool,
reservation: Option<(u32, u32)>,
}
impl Default for RunLocalWindow {
fn default() -> Self {
Self {
cached: None,
extent_size: 0,
next: 0,
end: 0,
target: INITIAL_RUN_LOCAL_WINDOW_TARGET,
}
}
}
impl RunLocalWindow {
fn release(&mut self) -> u32 {
let released = self.cached.as_ref().map_or(0, |cached| {
cached
.span
.release_run_territory_reservation(cached.generation, self.next, self.end)
});
*self = Self::default();
released
}
}
#[derive(Clone, Copy)]
struct LastLocalCache {
allocator_id: u64,
owner: u64,
pointer: *mut LocalCache,
}
impl Default for LastLocalCache {
fn default() -> Self {
Self {
allocator_id: 0,
owner: 0,
pointer: std::ptr::null_mut(),
}
}
}
struct LocalState {
caches: RefCell<HashMap<u64, Box<LocalCache>>>,
}
impl Default for LocalState {
fn default() -> Self {
Self {
caches: RefCell::new(HashMap::new()),
}
}
}
impl Drop for LocalState {
fn drop(&mut self) {
let _ = LAST_LOCAL_CACHE.try_with(|last| last.set(LastLocalCache::default()));
}
}
struct LocalCacheAccess {
#[cfg(debug_assertions)]
active: *const Cell<bool>,
}
impl Drop for LocalCacheAccess {
fn drop(&mut self) {
#[cfg(debug_assertions)]
unsafe {
(*self.active).set(false)
};
}
}
impl Drop for LocalCache {
fn drop(&mut self) {
let Some(inner) = self.inner.upgrade() else {
return;
};
for (class_index, class) in self.classes.iter_mut().enumerate() {
unsafe { class.remote.flush(class_index) };
class.magazine.flush(inner.config.recent_free_word_hints);
class.black_ring.flush(inner.config.recent_free_word_hints);
}
for window in &mut self.run_windows {
let released = window.release();
inner
.stats
.run_local_window_releases
.fetch_add(released as u64, Ordering::Relaxed);
}
for span in inner.address_tree.values() {
if inner.config.young_ring_spans != 0
&& span.kind() == SpanKind::Small
&& span.owner.load(Ordering::Acquire) == self.owner
&& span
.class_index()
.is_some_and(|class_index| SIZE_CLASSES[class_index] <= 4096)
{
if span.live() == 0 {
if span.try_recycle_empty_cohort(self.owner) {
inner.stats.cohort_recycles.fetch_add(1, Ordering::Relaxed);
}
continue;
}
if span.seal_small_cohort(self.owner, span.generation.load(Ordering::Acquire)) {
inner
.stats
.cohort_promotions
.fetch_add(1, Ordering::Relaxed);
}
}
let releasable = match span.kind() {
SpanKind::Run
| SpanKind::ReservedRun
| SpanKind::Dedicated
| SpanKind::DedicatedReserved => true,
SpanKind::Small | SpanKind::ReservedSmall | SpanKind::Free => span.live() == 0,
SpanKind::Retired => false,
};
if releasable {
let _ =
span.owner
.compare_exchange(self.owner, 0, Ordering::AcqRel, Ordering::Acquire);
}
}
}
}
static LOCAL_STATE: crate::tls::NativeThreadLocal<LocalState> =
crate::tls::NativeThreadLocal::new(LocalState::default);
thread_local! {
static LAST_LOCAL_CACHE: Cell<LastLocalCache> = const {
Cell::new(LastLocalCache {
allocator_id: 0,
owner: 0,
pointer: std::ptr::null_mut(),
})
};
}
#[inline]
pub(crate) fn thread_cache_available() -> bool {
LOCAL_STATE.try_with(|_| ()).is_ok()
}
#[inline(always)]
fn last_local_cache() -> LastLocalCache {
LAST_LOCAL_CACHE.with(Cell::get)
}
pub struct BoAllocator {
inner: Arc<Inner>,
}
impl Clone for BoAllocator {
fn clone(&self) -> Self {
Self {
inner: Arc::clone(&self.inner),
}
}
}
impl Drop for BoAllocator {
fn drop(&mut self) {
self.flush_current_remote_caches();
if Arc::strong_count(&self.inner) == 1 {
self.synchronize_current_black_accounting();
}
}
}
struct Inner {
id: u64,
config: Config,
backing: PlatformBacking,
topology: RwLock<Topology>,
address_tree: Arc<crate::topology::AddressTree>,
topology_snapshot: Atomic<TopologyReadSnapshot>,
stats: AtomicStats,
trim_epoch: AtomicU64,
free_claims_in_flight: AtomicUsize,
extent_control: AtomicUsize,
chunk_growth_requested: AtomicBool,
free_extent_hint: AtomicUsize,
empty_dedicated_committed: AtomicUsize,
dedicated_retention_epoch: AtomicU64,
collector: Collector,
}
impl BoAllocator {
pub fn new(config: Config) -> Result<Self, BoAllocError> {
let backing = PlatformBacking::new()?;
config.validate(backing.allocation_granularity())?;
let topology = Topology::new();
let address_tree = Arc::clone(&topology.tree);
Ok(Self {
inner: Arc::new(Inner {
id: NEXT_ALLOCATOR_ID.fetch_add(1, Ordering::Relaxed),
config,
backing,
topology: RwLock::new(topology),
address_tree,
topology_snapshot: Atomic::new(TopologyReadSnapshot::empty()),
stats: AtomicStats::default(),
trim_epoch: AtomicU64::new(0),
free_claims_in_flight: AtomicUsize::new(0),
extent_control: AtomicUsize::new(0),
chunk_growth_requested: AtomicBool::new(false),
free_extent_hint: AtomicUsize::new(0),
empty_dedicated_committed: AtomicUsize::new(0),
dedicated_retention_epoch: AtomicU64::new(1),
collector: Collector::new(),
}),
})
}
#[inline]
pub(crate) fn owns_address(&self, address: usize) -> bool {
self.inner.address_tree.containing(address).is_some()
}
#[inline]
pub fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, BoAllocError> {
if layout.size() == 0 {
let pointer =
NonNull::new(layout.align() as *mut u8).expect("Layout alignment is non-zero");
return Ok(NonNull::slice_from_raw_parts(pointer, 0));
}
if let Some(class_index) = self.inner.config.class_for(layout.size(), layout.align()) {
self.allocate_small(class_index, layout)
} else {
self.allocate_run(layout)
}
}
#[inline]
fn allocate_small(
&self,
class_index: usize,
layout: Layout,
) -> Result<NonNull<[u8]>, BoAllocError> {
if let Some(address) = self.try_allocate_local_cached(class_index, layout) {
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
self.allocate_small_slow(class_index, layout)
}
#[inline(never)]
fn allocate_small_slow(
&self,
class_index: usize,
layout: Layout,
) -> Result<NonNull<[u8]>, BoAllocError> {
let recent_limit = self.inner.config.recent_spans_per_class;
let (cached_address, owner, locality, rotate) = self.with_local_cache(|local| {
let owner = local.owner;
if local.classes[class_index].magazine.leased {
let pointer = local.classes[class_index].magazine.pointer;
let generation = local.classes[class_index].magazine.generation;
let span = unsafe { &*pointer };
if let Some((address, remote_drained)) = span.try_allocate_small_leased(
class_index,
owner,
generation,
self.inner.config.recent_free_word_hints,
) {
self.account_remote_drain(remote_drained);
let magazine = &mut local.classes[class_index].magazine;
magazine.record_allocation(layout);
magazine.fold_accounting(span);
self.refill_leased_magazine(magazine, span, class_index, owner, generation);
let locality = Some(LocalityHint {
address: span.base,
chunk_base: span.chunk_base,
});
return (Some(address), owner, locality, local.rng as usize);
}
let class = &mut local.classes[class_index];
class.magazine.fold_accounting(span);
let ring_limit = if SIZE_CLASSES[class_index] <= 4096 {
self.inner.config.black_span_ring_capacity
} else {
0
};
if ring_limit != 0 {
let entry = class.magazine.detach_exhausted_lease(span);
class.black_ring.retain(
entry,
ring_limit,
self.inner.config.recent_free_word_hints,
);
} else {
span.release_local_cache_lease();
class.magazine.clear();
}
}
let primary = local.classes[class_index].recent[0].as_ref();
let locality = primary.map(|cached| LocalityHint {
address: cached.span.base,
chunk_base: cached.span.chunk_base,
});
let mut hit = None;
for index in 0..recent_limit {
let Some(cached) = local.classes[class_index].recent[index].as_ref() else {
continue;
};
if let Some(address) = self.try_cached_small(cached, owner, class_index, layout) {
let pointer = cached.pointer();
let generation = cached.generation;
let span = unsafe { &*pointer };
self.try_establish_allocation_magazine(
local,
span,
class_index,
owner,
generation,
);
hit = Some((address, index));
break;
}
}
if let Some((_, index)) = hit {
if index != 0 {
local.classes[class_index].recent[..=index].rotate_right(1);
}
} else {
local.rng = xorshift(local.rng);
}
(
hit.map(|(address, _)| address),
owner,
locality,
local.rng as usize,
)
});
if let Some(address) = cached_address {
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if let Some((address, cached)) =
self.try_allocate_low_capacity_territory(class_index, layout, owner)?
{
self.cache_raw_span(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if let Some(locality_hint) = locality {
if let Some((address, cached)) = self.search_small_snapshot(
class_index,
layout,
owner,
rotate,
Some(locality_hint),
SnapshotSearchScope::Local,
) {
self.ensure_low_capacity_territory(class_index, owner, &cached);
self.cache_raw_span(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if let Some((address, cached)) = self.try_activate_reserved_snapshot(
class_index,
layout,
owner,
rotate,
Some(locality_hint),
)? {
self.ensure_low_capacity_territory(class_index, owner, &cached);
self.cache_raw_span(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if let Some((address, cached)) =
self.try_extend_small_territory(class_index, layout, owner, locality_hint)?
{
self.ensure_low_capacity_territory(class_index, owner, &cached);
self.cache_raw_span(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if let Some((address, cached)) =
self.try_allocate_territory_return(class_index, layout, owner)
{
self.ensure_low_capacity_territory(class_index, owner, &cached);
self.cache_returned_territory(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
}
if let Some((address, cached)) = self.search_small_snapshot(
class_index,
layout,
owner,
rotate,
locality,
SnapshotSearchScope::Global,
) {
self.ensure_low_capacity_territory(class_index, owner, &cached);
self.cache_raw_span(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if let Some((address, cached)) =
self.try_activate_reserved_snapshot(class_index, layout, owner, rotate, None)?
{
self.ensure_low_capacity_territory(class_index, owner, &cached);
self.cache_raw_span(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if let Some((address, cached)) =
self.search_small_exact(class_index, layout, owner, rotate, locality)?
{
self.ensure_low_capacity_territory(class_index, owner, &cached);
self.cache_raw_span(class_index, cached);
return self.finish_allocation(address, SIZE_CLASSES[class_index]);
}
if locality.is_some() {
self.remember_primary_territory(class_index);
}
let (span, address) = self.create_small_span(class_index, layout, owner, locality)?;
self.ensure_low_capacity_territory_from_span(class_index, owner, &span);
self.cache_span(class_index, &span);
self.finish_allocation(address, SIZE_CLASSES[class_index])
}
fn try_allocate_low_capacity_territory(
&self,
class_index: usize,
layout: Layout,
owner: u64,
) -> Result<Option<(usize, CachedSpan)>, BoAllocError> {
let Some(cache_index) = territory_cache_index(class_index) else {
return Ok(None);
};
if self.inner.config.low_capacity_page_queue_spans == 0 {
return Ok(None);
}
self.with_local_cache(|local| {
let cache = &mut local.low_capacity_territories[cache_index];
for offset in 0..cache.len {
let index = (cache.cursor + offset) % cache.len;
self.inner.stats.locality_probes.add(owner, 1);
let candidate = {
let Some(cached) = cache.spans[index].as_ref() else {
continue;
};
match cached.span.kind() {
SpanKind::Small => {
let mut conflicts = 0;
Ok(self.try_snapshot_candidate(
&cached.span,
class_index,
layout,
owner,
&mut conflicts,
))
}
SpanKind::ReservedSmall => self.try_activate_reserved_candidate(
&cached.span,
class_index,
layout,
owner,
),
_ => Ok(None),
}
}?;
if let Some((address, found)) = candidate {
if let Some(cached) = cache.spans[index].as_mut() {
cached.generation = found.generation;
}
cache.cursor = (index + 1) % cache.len;
self.inner.stats.locality_hits.add(owner, 1);
return Ok(Some((address, found)));
}
}
cache.spans.fill(None);
cache.len = 0;
cache.cursor = 0;
Ok(None)
})
}
fn ensure_low_capacity_territory(&self, class_index: usize, owner: u64, cached: &CachedSpan) {
self.ensure_low_capacity_territory_at(
class_index,
owner,
cached.span.base,
cached.span.chunk_base,
);
}
fn ensure_low_capacity_territory_from_span(
&self,
class_index: usize,
owner: u64,
span: &SpanHandle,
) {
self.ensure_low_capacity_territory_at(class_index, owner, span.base, span.chunk_base);
}
fn ensure_low_capacity_territory_at(
&self,
class_index: usize,
owner: u64,
address: usize,
chunk_base: usize,
) {
let Some(cache_index) = territory_cache_index(class_index) else {
return;
};
if self.inner.config.low_capacity_page_queue_spans == 0 {
return;
}
let needs_fill =
self.with_local_cache(|local| local.low_capacity_territories[cache_index].len == 0);
if !needs_fill {
return;
}
let limit = self
.inner
.config
.small_territory_spans(class_index)
.min(self.inner.config.low_capacity_page_queue_spans)
.min(MAX_LOW_CAPACITY_PAGE_QUEUE_SPANS);
let replacement = self.with_topology_snapshot(|snapshot| {
let spans = snapshot.class_spans(class_index);
let mut cache = TerritoryCache::default();
let insertion = spans.partition_point(|span| span.base < address);
if insertion == spans.len() || spans[insertion].base != address {
return cache;
}
let accepts = |span: &SpanHandle| {
let span_owner = span.owner.load(Ordering::Acquire);
span.chunk_base == chunk_base
&& match span.kind() {
SpanKind::Small => span_owner == 0 || span_owner == owner,
SpanKind::ReservedSmall => true,
_ => false,
}
};
let mut start = insertion;
while start > 0 && insertion - start + 1 < limit {
let previous = &spans[start - 1];
if previous.base + SMALL_SPAN_SIZE != spans[start].base || !accepts(previous) {
break;
}
start -= 1;
}
let mut expected = spans[start].base;
let mut seed_slot = 0;
for span in &spans[start..] {
if cache.len == limit || span.base != expected || !accepts(span) {
break;
}
if span.base == address {
seed_slot = cache.len;
}
cache.spans[cache.len] = Some(CachedSpan {
span: span.clone(),
generation: span.generation.load(Ordering::Acquire),
});
cache.len += 1;
expected += SMALL_SPAN_SIZE;
}
if cache.len != 0 {
cache.cursor = (seed_slot + 1) % cache.len;
}
cache
});
if replacement.len == 0 {
return;
}
self.with_local_cache(|local| {
let cache = &mut local.low_capacity_territories[cache_index];
if cache.len == 0 {
*cache = replacement;
}
});
}
fn try_allocate_territory_return(
&self,
class_index: usize,
layout: Layout,
owner: u64,
) -> Option<(usize, CachedSpan)> {
let cached =
self.with_local_cache(|local| local.classes[class_index].territory_return.clone())?;
self.inner.stats.locality_probes.add(owner, 1);
let mut conflicts = 0;
let result =
self.try_snapshot_candidate(&cached.span, class_index, layout, owner, &mut conflicts)?;
self.inner.stats.locality_hits.add(owner, 1);
Some(result)
}
#[inline]
fn try_allocate_local_cached(&self, class_index: usize, layout: Layout) -> Option<usize> {
let last = last_local_cache();
if last.allocator_id != self.inner.id || last.pointer.is_null() {
return None;
}
let local = unsafe { &mut *last.pointer };
#[cfg(debug_assertions)]
let active = std::ptr::addr_of!(local.active);
#[cfg(debug_assertions)]
assert!(!local.active.replace(true), "reentrant local cache access");
let _access = LocalCacheAccess {
#[cfg(debug_assertions)]
active,
};
let class = &mut local.classes[class_index];
let magazine = &mut class.magazine;
let (pointer, generation, address) = if let Some(exact) = magazine.pop() {
if magazine.len == 0 {
magazine.grow_after_drain(self.inner.config.local_magazine_capacity);
}
exact
} else if magazine.overflow_head != 0 {
let pointer = magazine.pointer;
let address =
unsafe { magazine.pop_overflow() }.expect("a non-empty overflow chain has a head");
(pointer, magazine.generation, address)
} else if let Some((pointer, generation, address)) =
unsafe { class.black_ring.pop(layout) }
{
let span = unsafe { &*pointer };
return Some(unsafe {
span.allocate_local_cached_address(last.owner, generation, class_index, address)
});
} else {
return class.remote.pop(layout);
};
let span = unsafe { &*pointer };
let address = unsafe {
span.allocate_local_cached_address(last.owner, generation, class_index, address)
};
magazine.record_allocation(layout);
Some(address)
}
#[cold]
#[inline(never)]
fn try_establish_allocation_magazine(
&self,
local: &mut LocalCache,
span: &SpanDesc,
class_index: usize,
owner: u64,
generation: u64,
) {
if self.inner.config.local_magazine_capacity == 0 {
return;
}
let class = &mut local.classes[class_index];
let magazine = &mut class.magazine;
if magazine.leased {
return;
}
if let Some(entry) = class
.black_ring
.take_by_pointer(span as *const SpanDesc, generation)
{
debug_assert_eq!(entry.base, span.base);
debug_assert_eq!(entry.free_head, 0);
debug_assert_eq!(entry.free_len, 0);
magazine.pointer = entry.pointer;
magazine.generation = entry.generation;
magazine.leased = true;
magazine.target = magazine.target.max(1);
magazine.live_delta = entry.live_delta;
magazine.requested_delta = entry.requested_delta;
self.refill_leased_magazine(magazine, span, class_index, owner, generation);
return;
}
if !span.try_acquire_local_cache_lease(owner, generation, class_index) {
return;
}
magazine.pointer = span as *const SpanDesc;
magazine.generation = generation;
magazine.leased = true;
magazine.target = magazine.target.max(1);
span.synchronize_remote_accounting();
self.refill_leased_magazine(magazine, span, class_index, owner, generation);
}
#[cold]
#[inline(never)]
fn refill_leased_magazine(
&self,
magazine: &mut LocalMagazine,
span: &SpanDesc,
class_index: usize,
owner: u64,
generation: u64,
) {
let target = magazine
.target
.min(self.inner.config.local_magazine_capacity)
.min(span.capacity() as usize);
while magazine.len < target {
let Some((address, remote_drained)) = span.reserve_small_for_local_cache(
class_index,
owner,
generation,
self.inner.config.recent_free_word_hints,
) else {
break;
};
self.account_remote_drain(remote_drained);
magazine.push(span as *const SpanDesc, generation, address, target);
}
}
fn try_activate_reserved_snapshot(
&self,
class_index: usize,
layout: Layout,
owner: u64,
rotate: usize,
locality: Option<LocalityHint>,
) -> Result<Option<(usize, CachedSpan)>, BoAllocError> {
self.with_topology_snapshot(|snapshot| {
self.try_activate_reserved_view(snapshot, class_index, layout, owner, rotate, locality)
})
}
fn try_activate_reserved_view(
&self,
snapshot: &TopologyReadSnapshot,
class_index: usize,
layout: Layout,
owner: u64,
rotate: usize,
locality: Option<LocalityHint>,
) -> Result<Option<(usize, CachedSpan)>, BoAllocError> {
let spans = snapshot.class_spans(class_index);
if spans.is_empty() {
return Ok(None);
}
if let Some(hint) = locality {
for owner_class in 0..3 {
let result = visit_locality_window(
spans,
hint,
self.inner.config.locality_window_spans,
|span| span.base,
|span| span.chunk_base,
|span| {
self.try_recycle_empty_cohort_candidate(span, class_index);
let span_owner = span.owner.load(Ordering::Acquire);
let candidate_class = if span_owner == owner {
0
} else if span_owner == 0 {
1
} else {
2
};
if candidate_class != owner_class {
return None;
}
self.try_activate_reserved_candidate(span, class_index, layout, owner)
.transpose()
},
);
match result {
Some(Ok(result)) => {
self.inner.stats.locality_hits.add(owner, 1);
return Ok(Some(result));
}
Some(Err(error)) => return Err(error),
None => {}
}
}
return Ok(None);
}
let mut start = 0;
let mut step = 1;
let mut conflicts = 0_u32;
let mut jumps = 0_u32;
let mut jumped = false;
let mut jump_rng = jump_seed(owner, rotate, class_index);
for owner_class in 0..3 {
let mut offset = 0;
while offset < spans.len() {
let span = &spans[(start + offset * step) % spans.len()];
offset += 1;
if span.kind() != SpanKind::ReservedSmall {
continue;
}
let span_owner = span.owner.load(Ordering::Acquire);
let candidate_class = if span_owner == owner {
0
} else if span_owner == 0 {
1
} else {
2
};
if candidate_class != owner_class {
continue;
}
self.inner.stats.global_candidate_probes.add(owner, 1);
if jumped {
self.inner.stats.post_jump_probes.add(owner, 1);
}
if let Some(result) =
self.try_activate_reserved_candidate(span, class_index, layout, owner)?
{
if jumped {
self.inner.stats.jump_successes.add(owner, 1);
}
return Ok(Some(result));
}
conflicts += 1;
if conflicts >= self.inner.config.conflict_threshold
&& jumps < self.inner.config.max_random_jumps
{
jump_rng = xorshift(jump_rng);
if jump_rng % u64::from(self.inner.config.jump_probability_denominator) == 0 {
start = jump_rng as usize % spans.len();
jump_rng = xorshift(jump_rng);
step = coprime_step(jump_rng as usize, spans.len());
offset = 0;
jumps += 1;
jumped = true;
self.inner
.stats
.random_jumps
.fetch_add(1, Ordering::Relaxed);
}
}
}
}
Ok(None)
}
fn search_small_exact(
&self,
class_index: usize,
layout: Layout,
owner: u64,
rotate: usize,
locality: Option<LocalityHint>,
) -> Result<Option<(usize, CachedSpan)>, BoAllocError> {
let view = TopologyReadSnapshot::from_tree(&self.inner.address_tree);
if locality.is_some() {
if let Some(result) = self.search_small_snapshot_view(
&view,
class_index,
layout,
owner,
rotate,
locality,
SnapshotSearchScope::Local,
) {
return Ok(Some(result));
}
if let Some(result) = self.try_activate_reserved_view(
&view,
class_index,
layout,
owner,
rotate,
locality,
)? {
return Ok(Some(result));
}
}
if let Some(result) = self.search_small_snapshot_view(
&view,
class_index,
layout,
owner,
rotate,
locality,
SnapshotSearchScope::Global,
) {
return Ok(Some(result));
}
self.try_activate_reserved_view(&view, class_index, layout, owner, rotate, None)
}
fn try_activate_reserved_candidate(
&self,
span: &SpanHandle,
class_index: usize,
layout: Layout,
owner: u64,
) -> Result<Option<(usize, CachedSpan)>, BoAllocError> {
if span.kind() != SpanKind::ReservedSmall || span.class_index() != Some(class_index) {
return Ok(None);
}
let previous_owner = span.owner.load(Ordering::Acquire);
if previous_owner != 0
&& previous_owner != owner
&& span.record_foreign_miss() < self.inner.config.red_cold_slow_paths
{
return Ok(None);
}
if !span.try_freeze_reserved(class_index, previous_owner) {
return Ok(None);
}
if previous_owner != owner
&& span
.owner
.compare_exchange(previous_owner, owner, Ordering::AcqRel, Ordering::Acquire)
.is_err()
{
span.unfreeze();
return Ok(None);
}
if let Err(error) = unsafe { self.inner.backing.commit(span.base, span.size) } {
if previous_owner != owner {
span.owner.store(previous_owner, Ordering::Release);
}
span.unfreeze();
return Err(error);
}
let generation = span.advance_reserved_generation();
if small_payload_offset(class_index) != 0 {
let anchor = SpanAnchor::new(self.inner.id, span.as_ptr(), generation, class_index);
unsafe { std::ptr::write(span.base as *mut SpanAnchor, anchor) };
}
let address = span.activate_reserved_with_first_allocation(layout);
self.inner
.stats
.committed
.fetch_add(span.size, Ordering::Relaxed);
self.inner
.stats
.reserved_span_activations
.fetch_add(1, Ordering::Relaxed);
if previous_owner != 0 && previous_owner != owner {
self.inner.stats.steals.fetch_add(1, Ordering::Relaxed);
}
Ok(Some((
address,
CachedSpan {
span: span.clone(),
generation,
},
)))
}
#[allow(clippy::too_many_arguments)]
fn search_small_snapshot(
&self,
class_index: usize,
layout: Layout,
owner: u64,
rotate: usize,
locality: Option<LocalityHint>,
scope: SnapshotSearchScope,
) -> Option<(usize, CachedSpan)> {
self.with_topology_snapshot(|snapshot| {
self.search_small_snapshot_view(
snapshot,
class_index,
layout,
owner,
rotate,
locality,
scope,
)
})
}
#[allow(clippy::too_many_arguments)]
fn search_small_snapshot_view(
&self,
snapshot: &TopologyReadSnapshot,
class_index: usize,
layout: Layout,
owner: u64,
rotate: usize,
locality: Option<LocalityHint>,
scope: SnapshotSearchScope,
) -> Option<(usize, CachedSpan)> {
let spans = snapshot.class_spans(class_index);
if spans.is_empty() {
return None;
}
let mut conflicts = 0_u32;
if scope == SnapshotSearchScope::Local {
let hint = locality.expect("local snapshot search requires an address hint");
for owner_class in 0..3 {
let result = visit_locality_window(
spans,
hint,
self.inner.config.locality_window_spans,
|span| span.base,
|span| span.chunk_base,
|span| {
let span_owner = span.owner.load(Ordering::Acquire);
let candidate_class = if span_owner == owner {
0
} else if span_owner == 0 {
1
} else if span.kind() == SpanKind::Small && span.live() == 0 {
2
} else {
3
};
if candidate_class != owner_class {
return None;
}
self.inner.stats.locality_probes.add(owner, 1);
if let Some(result) = self.try_snapshot_candidate(
span,
class_index,
layout,
owner,
&mut conflicts,
) {
self.inner.stats.locality_hits.add(owner, 1);
return Some(result);
}
None
},
);
if result.is_some() {
return result;
}
}
return None;
}
self.inner.stats.global_searches.add(owner, 1);
let mut start = 0;
let mut step = 1;
let mut jumps = 0_u32;
let mut jumped = false;
let mut jump_rng = jump_seed(owner, rotate, class_index);
for owner_class in 0..3 {
let mut offset = 0;
while offset < spans.len() {
let span = &spans[(start + offset * step) % spans.len()];
offset += 1;
self.try_recycle_empty_cohort_candidate(span, class_index);
let span_owner = span.owner.load(Ordering::Acquire);
let candidate_class = if span_owner == owner {
0
} else if span_owner == 0 {
1
} else if span.kind() == SpanKind::Small && span.live() == 0 {
2
} else {
3
};
if candidate_class != owner_class {
continue;
}
self.inner.stats.global_candidate_probes.add(owner, 1);
if jumped {
self.inner.stats.post_jump_probes.add(owner, 1);
}
let conflicts_before = conflicts;
if let Some(result) =
self.try_snapshot_candidate(span, class_index, layout, owner, &mut conflicts)
{
if jumped {
self.inner.stats.jump_successes.add(owner, 1);
}
return Some(result);
}
if conflicts > conflicts_before
&& conflicts >= self.inner.config.conflict_threshold
&& jumps < self.inner.config.max_random_jumps
{
jump_rng = xorshift(jump_rng);
if jump_rng % u64::from(self.inner.config.jump_probability_denominator) == 0 {
start = jump_rng as usize % spans.len();
jump_rng = xorshift(jump_rng);
step = coprime_step(jump_rng as usize, spans.len());
offset = 0;
jumps += 1;
jumped = true;
self.inner
.stats
.random_jumps
.fetch_add(1, Ordering::Relaxed);
}
}
}
}
None
}
fn try_snapshot_candidate(
&self,
span: &SpanHandle,
class_index: usize,
layout: Layout,
owner: u64,
conflicts: &mut u32,
) -> Option<(usize, CachedSpan)> {
let current_owner = span.owner.load(Ordering::Acquire);
let reclaimed_empty_black = current_owner != 0
&& current_owner != owner
&& span.try_transfer_empty_small(class_index, current_owner, owner);
let can_claim = current_owner == owner
|| reclaimed_empty_black
|| (current_owner == 0
&& span
.owner
.compare_exchange(0, owner, Ordering::AcqRel, Ordering::Acquire)
.is_ok());
if !can_claim {
*conflicts += 1;
self.inner
.stats
.cas_failures
.fetch_add(1, Ordering::Relaxed);
return None;
}
if reclaimed_empty_black {
self.inner
.stats
.empty_black_reclaims
.fetch_add(1, Ordering::Relaxed);
self.inner.stats.steals.fetch_add(1, Ordering::Relaxed);
}
if !span.has_capacity() {
return None;
}
let generation = span.generation.load(Ordering::Acquire);
let Some(address) =
self.try_allocate_from_span(span, class_index, layout, owner, generation)
else {
*conflicts += 1;
return None;
};
Some((
address,
CachedSpan {
span: span.clone(),
generation,
},
))
}
fn try_recycle_empty_cohort_candidate(&self, span: &SpanHandle, class_index: usize) {
if self.cohort_limit(class_index) == 0 || !span.is_cohort_sealed() || span.live() != 0 {
return;
}
let owner = span.owner.load(Ordering::Acquire);
if owner != 0 && span.try_recycle_empty_cohort(owner) {
self.inner
.stats
.cohort_recycles
.fetch_add(1, Ordering::Relaxed);
}
}
fn try_cached_small(
&self,
cached: &CachedSpan,
owner: u64,
class_index: usize,
layout: Layout,
) -> Option<usize> {
let span = &*cached.span;
let address =
self.try_allocate_from_span(span, class_index, layout, owner, cached.generation)?;
Some(address)
}
fn try_allocate_from_span(
&self,
span: &SpanDesc,
class_index: usize,
layout: Layout,
owner: u64,
generation: u64,
) -> Option<usize> {
let (address, remote_drained) = span.try_allocate_small(
class_index,
layout,
owner,
generation,
self.inner.config.recent_free_word_hints,
)?;
self.account_remote_drain(remote_drained);
Some(address)
}
fn account_remote_drain(&self, remote_drained: u32) {
if remote_drained == 0 {
return;
}
self.inner
.stats
.remote_batches_drained
.fetch_add(1, Ordering::Relaxed);
self.inner
.stats
.remote_blocks_drained
.fetch_add(remote_drained as u64, Ordering::Relaxed);
}
fn try_begin_extent_transaction(&self) -> Option<ExtentTransaction<'_>> {
let mut control = self.inner.extent_control.load(Ordering::Acquire);
loop {
if control & MAINTENANCE_BIT != 0 {
return None;
}
debug_assert!(control < MAINTENANCE_BIT - 1);
match self.inner.extent_control.compare_exchange_weak(
control,
control + 1,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(ExtentTransaction(&self.inner)),
Err(actual) => control = actual,
}
}
}
fn begin_maintenance(&self) -> MaintenanceGate<'_> {
let previous = self
.inner
.extent_control
.fetch_or(MAINTENANCE_BIT, Ordering::AcqRel);
debug_assert_eq!(previous & MAINTENANCE_BIT, 0);
while self.inner.extent_control.load(Ordering::Acquire) != MAINTENANCE_BIT {
std::thread::yield_now();
}
MaintenanceGate(&self.inner)
}
fn create_small_span(
&self,
class_index: usize,
layout: Layout,
owner: u64,
locality: Option<LocalityHint>,
) -> Result<(SpanHandle, usize), BoAllocError> {
loop {
if self.inner.chunk_growth_requested.load(Ordering::Acquire) {
std::thread::yield_now();
continue;
}
let Some(transaction) = self.try_begin_extent_transaction() else {
std::thread::yield_now();
continue;
};
let candidate = self.inner.address_tree.find_free_fit_near(
SMALL_SPAN_SIZE,
SMALL_SPAN_SIZE,
locality,
Some(owner),
);
let Some((free, address)) = candidate else {
let pending = self
.inner
.address_tree
.has_pending_free_fit(SMALL_SPAN_SIZE, SMALL_SPAN_SIZE)
|| self.inner.free_claims_in_flight.load(Ordering::Acquire) != 0;
drop(transaction);
if pending {
std::thread::yield_now();
continue;
}
if !self.ensure_chunk_for_extent(SMALL_SPAN_SIZE, SMALL_SPAN_SIZE)? {
std::thread::yield_now();
}
continue;
};
self.inner
.free_claims_in_flight
.fetch_add(1, Ordering::AcqRel);
if !free.try_claim_free() {
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
drop(transaction);
std::hint::spin_loop();
continue;
}
let free_end = free.base + free.size;
let active_end = address + SMALL_SPAN_SIZE;
let reserve_count = self
.inner
.config
.small_territory_spans(class_index)
.saturating_sub(1)
.min((free_end - active_end) / SMALL_SPAN_SIZE);
let territory_end = active_end + reserve_count * SMALL_SPAN_SIZE;
let extension_count = self
.inner
.config
.adaptive_small_territory_spans(class_index)
.saturating_sub(reserve_count + 1)
.min((free_end - territory_end) / SMALL_SPAN_SIZE);
let claimed_end = territory_end + extension_count * SMALL_SPAN_SIZE;
if let Err(error) = unsafe { self.inner.backing.commit(address, SMALL_SPAN_SIZE) } {
free.unfreeze();
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
return Err(error);
}
let span = self.inner.address_tree.allocate_span(SpanDesc::small(
address,
free.chunk_base,
class_index,
SIZE_CLASSES[class_index],
));
span.owner.store(owner, Ordering::Release);
let generation = span.generation.load(Ordering::Relaxed);
if small_payload_offset(class_index) != 0 {
let anchor = SpanAnchor::new(self.inner.id, span.as_ptr(), generation, class_index);
unsafe { std::ptr::write(span.base as *mut SpanAnchor, anchor) };
}
let allocation = self
.try_allocate_from_span(&span, class_index, layout, owner, generation)
.expect("an unpublished new small span has capacity");
let source_owner = free.owner.load(Ordering::Acquire);
if source_owner != 0 && source_owner != owner {
self.inner.stats.steals.fetch_add(1, Ordering::Relaxed);
}
let prefix = (address > free.base).then(|| {
let prefix = self.inner.address_tree.allocate_span(SpanDesc::free(
free.base,
address - free.base,
free.chunk_base,
));
prefix.owner.store(source_owner, Ordering::Release);
prefix
});
let extension = (extension_count != 0).then(|| {
let extension = self.inner.address_tree.allocate_span(SpanDesc::free(
territory_end,
extension_count * SMALL_SPAN_SIZE,
free.chunk_base,
));
extension.owner.store(owner, Ordering::Release);
extension
});
let suffix = (claimed_end < free_end).then(|| {
let suffix = self.inner.address_tree.allocate_span(SpanDesc::free(
claimed_end,
free_end - claimed_end,
free.chunk_base,
));
suffix.owner.store(source_owner, Ordering::Release);
suffix
});
let mut reserved_spans = Vec::with_capacity(reserve_count);
for index in 0..reserve_count {
let base = active_end + index * SMALL_SPAN_SIZE;
let reserved = self
.inner
.address_tree
.allocate_span(SpanDesc::reserved_small(
base,
free.chunk_base,
class_index,
SIZE_CLASSES[class_index],
));
reserved.owner.store(owner, Ordering::Release);
reserved_spans.push(reserved);
}
let mut replacements = Vec::with_capacity(
1 + reserved_spans.len()
+ usize::from(prefix.is_some())
+ usize::from(extension.is_some())
+ usize::from(suffix.is_some()),
);
if let Some(prefix) = &prefix {
replacements.push(prefix.clone());
}
replacements.push(span.clone());
replacements.extend(reserved_spans.iter().cloned());
if let Some(extension) = &extension {
replacements.push(extension.clone());
}
if let Some(suffix) = &suffix {
replacements.push(suffix.clone());
}
assert!(
self.inner.address_tree.replace_batch(&free, &replacements),
"an exclusively claimed free extent remains replaceable"
);
free.retire();
if let Some(hint) = prefix.as_ref().or(suffix.as_ref()) {
self.inner
.free_extent_hint
.store(hint.base, Ordering::Release);
}
self.inner.stats.splits.fetch_add(
(reserve_count
+ usize::from(prefix.is_some())
+ usize::from(extension.is_some())
+ usize::from(suffix.is_some())) as u64,
Ordering::Relaxed,
);
self.inner
.stats
.committed
.fetch_add(SMALL_SPAN_SIZE, Ordering::Relaxed);
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
drop(transaction);
self.publish_address_tree_snapshot();
return Ok((span, allocation));
}
}
fn try_extend_small_territory(
&self,
class_index: usize,
layout: Layout,
owner: u64,
locality: LocalityHint,
) -> Result<Option<(usize, CachedSpan)>, BoAllocError> {
let initial_limit = self.inner.config.small_territory_spans(class_index);
let target = self
.inner
.config
.adaptive_small_territory_spans(class_index);
let extension_limit = target.saturating_sub(initial_limit);
if extension_limit == 0 {
return Ok(None);
}
let Some((tail, existing)) = self.with_topology_snapshot(|snapshot| {
let spans = snapshot.class_spans(class_index);
let seed = spans
.binary_search_by_key(&locality.address, |span| span.base)
.ok()?;
let accepts = |span: &SpanHandle| {
span.chunk_base == locality.chunk_base
&& span.class_index() == Some(class_index)
&& matches!(span.kind(), SpanKind::Small | SpanKind::ReservedSmall)
&& span.owner.load(Ordering::Acquire) == owner
};
if !accepts(&spans[seed]) {
return None;
}
let mut start = seed;
while start > 0
&& spans[start - 1].base + SMALL_SPAN_SIZE == spans[start].base
&& accepts(&spans[start - 1])
{
start -= 1;
}
let mut end = seed + 1;
while end < spans.len()
&& spans[end - 1].base + SMALL_SPAN_SIZE == spans[end].base
&& accepts(&spans[end])
{
end += 1;
}
Some((spans[end - 1].clone(), end - start))
}) else {
return Ok(None);
};
if existing >= target {
return Ok(None);
}
let extension_count = (target - existing).min(extension_limit);
let extension_base = tail.base + SMALL_SPAN_SIZE;
if self.inner.chunk_growth_requested.load(Ordering::Acquire) {
return Ok(None);
}
let Some(transaction) = self.try_begin_extent_transaction() else {
return Ok(None);
};
let Some(free) = self.inner.address_tree.get(extension_base) else {
return Ok(None);
};
let source_owner = free.owner.load(Ordering::Acquire);
if free.kind() != SpanKind::Free
|| free.chunk_base != locality.chunk_base
|| free.base != extension_base
|| free.size < extension_count * SMALL_SPAN_SIZE
|| (source_owner != 0 && source_owner != owner)
|| tail.kind() == SpanKind::Retired
|| tail.owner.load(Ordering::Acquire) != owner
{
return Ok(None);
}
self.inner
.free_claims_in_flight
.fetch_add(1, Ordering::AcqRel);
if !free.try_claim_free() {
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
return Ok(None);
}
if let Err(error) = unsafe { self.inner.backing.commit(extension_base, SMALL_SPAN_SIZE) } {
free.unfreeze();
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
return Err(error);
}
let active = self.inner.address_tree.allocate_span(SpanDesc::small(
extension_base,
free.chunk_base,
class_index,
SIZE_CLASSES[class_index],
));
active.owner.store(owner, Ordering::Release);
let generation = active.generation.load(Ordering::Relaxed);
if small_payload_offset(class_index) != 0 {
let anchor = SpanAnchor::new(self.inner.id, active.as_ptr(), generation, class_index);
unsafe { std::ptr::write(active.base as *mut SpanAnchor, anchor) };
}
let allocation = self
.try_allocate_from_span(&active, class_index, layout, owner, generation)
.expect("an unpublished extension span has capacity");
let mut replacements = Vec::with_capacity(extension_count + 1);
replacements.push(active.clone());
for index in 1..extension_count {
let reserved = self
.inner
.address_tree
.allocate_span(SpanDesc::reserved_small(
extension_base + index * SMALL_SPAN_SIZE,
free.chunk_base,
class_index,
SIZE_CLASSES[class_index],
));
reserved.owner.store(owner, Ordering::Release);
replacements.push(reserved);
}
let extension_end = extension_base + extension_count * SMALL_SPAN_SIZE;
let free_end = free.base + free.size;
let suffix = (extension_end < free_end).then(|| {
let suffix = self.inner.address_tree.allocate_span(SpanDesc::free(
extension_end,
free_end - extension_end,
free.chunk_base,
));
suffix.owner.store(source_owner, Ordering::Release);
suffix
});
if let Some(suffix) = &suffix {
replacements.push(suffix.clone());
}
assert!(
self.inner.address_tree.replace_batch(&free, &replacements),
"an exclusively claimed adjacent free extent remains replaceable"
);
free.retire();
if let Some(suffix) = &suffix {
self.inner
.free_extent_hint
.store(suffix.base, Ordering::Release);
}
self.inner.stats.splits.fetch_add(
(extension_count.saturating_sub(1) + usize::from(suffix.is_some())) as u64,
Ordering::Relaxed,
);
self.inner
.stats
.territory_extensions
.fetch_add(1, Ordering::Relaxed);
self.inner
.stats
.territory_extension_spans
.fetch_add(extension_count as u64, Ordering::Relaxed);
self.inner
.stats
.committed
.fetch_add(SMALL_SPAN_SIZE, Ordering::Relaxed);
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
drop(transaction);
self.publish_address_tree_snapshot();
Ok(Some((
allocation,
CachedSpan {
span: active,
generation,
},
)))
}
fn allocate_run(&self, layout: Layout) -> Result<NonNull<[u8]>, BoAllocError> {
let page = self.inner.backing.page_size();
let header = size_of::<RunHeader>();
let needed = layout
.size()
.checked_add(header)
.and_then(|value| value.checked_add(layout.align() - 1))
.ok_or(BoAllocError::AddressSpaceExhausted)?;
let extent_size = align_up(needed, page).ok_or(BoAllocError::AddressSpaceExhausted)?;
let dedicated = layout.size() >= self.inner.config.large_threshold
|| layout.align() > self.inner.backing.allocation_granularity()
|| extent_size > self.inner.config.chunk_size;
let owner = self.with_local_cache(|local| local.owner);
if let Some((span, user, usable)) =
self.try_reuse_cached_run(layout, extent_size, dedicated, owner)?
{
return self.finish_run_allocation(&span, user, usable);
}
if let Some((span, user, usable)) =
self.try_reuse_run_snapshot(layout, extent_size, dedicated, owner)?
{
self.cache_run(dedicated, &span);
return self.finish_run_allocation(&span, user, usable);
}
if let Some((span, user, usable)) =
self.try_reuse_run_tree(layout, extent_size, dedicated, owner)?
{
self.cache_run(dedicated, &span);
return self.finish_run_allocation(&span, user, usable);
}
let (span, user, usable) = if dedicated {
self.create_live_dedicated(layout, extent_size, owner)?
} else {
self.create_live_chunk_run(layout, extent_size, page, owner)?
};
self.cache_run(dedicated, &span);
self.finish_run_allocation(&span, user, usable)
}
fn try_reuse_run_tree(
&self,
layout: Layout,
extent_size: usize,
dedicated: bool,
owner: u64,
) -> Result<Option<(SpanHandle, usize, usize)>, BoAllocError> {
let mut spans = self.inner.address_tree.values();
if dedicated {
spans.sort_unstable_by_key(|span| span.size);
}
for owner_class in 0..3 {
for span in &spans {
let current_owner = span.owner.load(Ordering::Acquire);
let class = if current_owner == owner {
0
} else if current_owner == 0 {
1
} else {
2
};
if class != owner_class || !self.try_claim_run_owner(span, owner, owner_class == 2)
{
continue;
}
if let Some(prepared) =
self.try_prepare_run(span, layout, extent_size, dedicated, owner, 1)?
{
return Ok(Some((span.clone(), prepared.user, prepared.usable)));
}
}
}
Ok(None)
}
fn create_live_chunk_run(
&self,
layout: Layout,
extent_size: usize,
page: usize,
owner: u64,
) -> Result<(SpanHandle, usize, usize), BoAllocError> {
loop {
if self.inner.chunk_growth_requested.load(Ordering::Acquire) {
std::thread::yield_now();
continue;
}
let Some(transaction) = self.try_begin_extent_transaction() else {
std::thread::yield_now();
continue;
};
let hint = self.inner.free_extent_hint.load(Ordering::Acquire);
let hinted = (hint != 0)
.then(|| self.inner.address_tree.get(hint))
.flatten()
.and_then(|span| {
if !span.is_available_free() || span.owner.load(Ordering::Acquire) != owner {
return None;
}
let address = align_up(span.base, page)?;
(address.checked_add(extent_size)? <= span.base + span.size)
.then_some((span, address))
});
let candidate = hinted.or_else(|| {
self.inner
.address_tree
.find_free_fit_near(extent_size, page, None, Some(owner))
});
let Some((free, address)) = candidate else {
let pending = self
.inner
.address_tree
.has_pending_free_fit(extent_size, page)
|| self.inner.free_claims_in_flight.load(Ordering::Acquire) != 0;
drop(transaction);
if pending {
std::thread::yield_now();
continue;
}
if !self.ensure_chunk_for_extent(extent_size, page)? {
std::thread::yield_now();
}
continue;
};
self.inner
.free_claims_in_flight
.fetch_add(1, Ordering::AcqRel);
if !free.try_claim_free() {
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
drop(transaction);
std::hint::spin_loop();
continue;
}
let available_extents = (free.base + free.size - address) / extent_size;
let initial_count = INITIAL_RUN_TERRITORY_EXTENTS.min(available_extents);
let extension_count = self
.inner
.config
.adaptive_run_territory_extension_extents
.min(available_extents - initial_count);
let territory_count = initial_count + extension_count;
let territory_size = extent_size * territory_count;
if let Err(error) = unsafe { self.inner.backing.commit(address, extent_size) } {
free.unfreeze();
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
return Err(error);
}
let source_owner = free.owner.load(Ordering::Acquire);
let end = address + territory_size;
let free_end = free.base + free.size;
let prefix = (address > free.base).then(|| {
let prefix = self.inner.address_tree.allocate_span(SpanDesc::free(
free.base,
address - free.base,
free.chunk_base,
));
prefix.owner.store(source_owner, Ordering::Release);
prefix
});
let suffix = (end < free_end).then(|| {
let suffix = self.inner.address_tree.allocate_span(SpanDesc::free(
end,
free_end - end,
free.chunk_base,
));
suffix.owner.store(source_owner, Ordering::Release);
suffix
});
if extension_count != 0 {
let span = self
.inner
.address_tree
.allocate_span(SpanDesc::run_territory(
address,
territory_size,
free.chunk_base,
extent_size,
territory_count as u32,
));
span.owner.store(owner, Ordering::Release);
let user = align_up(address + size_of::<RunHeader>(), layout.align())
.ok_or(BoAllocError::AddressSpaceExhausted)?;
let usable = address + extent_size - user;
assert!(span.try_account_run_allocation(layout.size(), usable));
let mut replacements = Vec::with_capacity(
1 + usize::from(prefix.is_some()) + usize::from(suffix.is_some()),
);
if let Some(prefix) = &prefix {
replacements.push(prefix.clone());
}
replacements.push(span.clone());
if let Some(suffix) = &suffix {
replacements.push(suffix.clone());
}
assert!(
self.inner.address_tree.replace_batch(&free, &replacements),
"an exclusively claimed free extent remains replaceable"
);
free.retire();
if let Some(hint) = prefix.as_ref().or(suffix.as_ref()) {
self.inner
.free_extent_hint
.store(hint.base, Ordering::Release);
}
self.inner.stats.splits.fetch_add(
(usize::from(prefix.is_some()) + usize::from(suffix.is_some())) as u64,
Ordering::Relaxed,
);
self.inner
.stats
.committed
.fetch_add(extent_size, Ordering::Relaxed);
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
drop(transaction);
self.cache_run(false, &span);
return Ok((span, user, usable));
}
let span = self.inner.address_tree.allocate_span(SpanDesc::run(
address,
extent_size,
free.chunk_base,
false,
));
span.owner.store(owner, Ordering::Release);
let user = align_up(address + size_of::<RunHeader>(), layout.align())
.ok_or(BoAllocError::AddressSpaceExhausted)?;
let usable = address + extent_size - user;
assert!(span.try_account_run_allocation(layout.size(), usable));
let mut local_territory = Vec::with_capacity(initial_count.saturating_sub(1));
for index in 1..initial_count {
let base = address + index * extent_size;
let reserved = self
.inner
.address_tree
.allocate_span(SpanDesc::reserved_run(base, extent_size, free.chunk_base));
reserved.owner.store(owner, Ordering::Release);
local_territory.push(reserved);
}
let mut replacements = Vec::with_capacity(
1 + local_territory.len()
+ usize::from(prefix.is_some())
+ usize::from(suffix.is_some()),
);
if let Some(prefix) = &prefix {
replacements.push(prefix.clone());
}
replacements.push(span.clone());
replacements.extend(local_territory.iter().cloned());
if let Some(suffix) = &suffix {
replacements.push(suffix.clone());
}
assert!(
self.inner.address_tree.replace_batch(&free, &replacements),
"an exclusively claimed free extent remains replaceable"
);
free.retire();
if let Some(hint) = prefix.as_ref().or(suffix.as_ref()) {
self.inner
.free_extent_hint
.store(hint.base, Ordering::Release);
}
self.inner.stats.splits.fetch_add(
(usize::from(prefix.is_some()) + usize::from(suffix.is_some())) as u64,
Ordering::Relaxed,
);
self.inner
.stats
.committed
.fetch_add(extent_size, Ordering::Relaxed);
self.inner
.free_claims_in_flight
.fetch_sub(1, Ordering::Release);
drop(transaction);
for reserved in &local_territory {
self.cache_run(false, reserved);
}
self.cache_run(false, &span);
if let Some(first_reserved) = local_territory.first() {
self.prefer_cached_run(first_reserved);
}
return Ok((span, user, usable));
}
}
fn ensure_chunk_for_extent(&self, size: usize, align: usize) -> Result<bool, BoAllocError> {
if self
.inner
.chunk_growth_requested
.compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
.is_err()
{
return Ok(false);
}
let result = loop {
match self.inner.topology.try_write() {
Ok(mut topology) => {
let _maintenance = self.begin_maintenance();
if topology
.find_free_fit_near(size, align, None, None)
.is_some()
{
break Ok(());
}
let base =
match unsafe { self.inner.backing.reserve(self.inner.config.chunk_size) } {
Ok(base) => base,
Err(error) => break Err(error),
};
let chunk = ChunkRecord {
base,
size: self.inner.config.chunk_size,
};
topology.chunks.push(chunk);
let free = topology
.tree
.allocate_span(SpanDesc::free(base, chunk.size, base));
topology.tree.insert(base, free);
self.inner.free_extent_hint.store(base, Ordering::Release);
self.inner
.stats
.reserved
.fetch_add(chunk.size, Ordering::Relaxed);
break Ok(());
}
Err(std::sync::TryLockError::WouldBlock) => {
if self
.inner
.address_tree
.find_free_fit_near(size, align, None, None)
.is_some()
{
break Ok(());
}
std::thread::yield_now();
}
Err(std::sync::TryLockError::Poisoned(_)) => {
panic!("topology lock poisoned")
}
}
};
self.inner
.chunk_growth_requested
.store(false, Ordering::Release);
result.map(|()| true)
}
fn create_live_dedicated(
&self,
layout: Layout,
minimum_size: usize,
owner: u64,
) -> Result<(SpanHandle, usize, usize), BoAllocError> {
let granularity = self.inner.backing.allocation_granularity();
let reserve_size =
align_up(minimum_size, granularity).ok_or(BoAllocError::AddressSpaceExhausted)?;
let base = unsafe { self.inner.backing.reserve(reserve_size)? };
if let Err(error) = unsafe { self.inner.backing.commit(base, reserve_size) } {
let _ = unsafe { self.inner.backing.release(base, reserve_size) };
return Err(error);
}
let span =
self.inner
.address_tree
.allocate_span(SpanDesc::run(base, reserve_size, base, true));
span.owner.store(owner, Ordering::Release);
let user = align_up(base + size_of::<RunHeader>(), layout.align())
.ok_or(BoAllocError::AddressSpaceExhausted)?;
let usable = base + reserve_size - user;
assert!(span.try_account_run_allocation(layout.size(), usable));
self.inner.address_tree.insert(base, span.clone());
self.inner
.stats
.reserved
.fetch_add(reserve_size, Ordering::Relaxed);
self.inner
.stats
.committed
.fetch_add(reserve_size, Ordering::Relaxed);
Ok((span, user, usable))
}
fn try_allocate_run_window(
&self,
local: &mut LocalCache,
layout: Layout,
extent_size: usize,
) -> Option<(SpanHandle, usize, usize)> {
if self.inner.config.run_local_window_capacity <= 1 {
return None;
}
for window in &mut local.run_windows {
if window.extent_size != extent_size || window.next >= window.end {
continue;
}
let Some(cached) = window.cached.as_ref().cloned() else {
continue;
};
let index = window.next;
if let Some((user, usable)) = cached.span.try_allocate_reserved_run_territory_index(
layout,
cached.generation,
index,
) {
window.next += 1;
if window.next == window.end {
window.target = window
.target
.saturating_mul(2)
.min(self.inner.config.run_local_window_capacity as u32);
}
self.inner.stats.run_local_window_hits.add(local.owner, 1);
return Some((cached.span, user, usable));
}
let released = window.release();
self.inner
.stats
.run_local_window_releases
.fetch_add(released as u64, Ordering::Relaxed);
}
None
}
fn run_window_target(
&self,
local: &LocalCache,
cached: &CachedSpan,
extent_size: usize,
) -> u32 {
let maximum = self.inner.config.run_local_window_capacity as u32;
if maximum <= 1 {
return 1;
}
local
.run_windows
.iter()
.find(|window| {
window.extent_size == extent_size
&& window.cached.as_ref().is_some_and(|entry| {
entry.pointer() == cached.pointer() && entry.generation == cached.generation
})
})
.map_or(INITIAL_RUN_LOCAL_WINDOW_TARGET, |window| window.target)
.min(maximum)
.max(1)
}
fn install_run_window(
&self,
local: &mut LocalCache,
cached: &CachedSpan,
extent_size: usize,
next: u32,
end: u32,
) {
debug_assert!(next < end);
let same = local.run_windows.iter().position(|window| {
window.cached.as_ref().is_some_and(|entry| {
entry.pointer() == cached.pointer() && entry.generation == cached.generation
})
});
let empty = local
.run_windows
.iter()
.position(|window| window.cached.is_none());
let index = same.or(empty).unwrap_or_else(|| {
let index = local.run_window_cursor;
local.run_window_cursor = (local.run_window_cursor + 1) % RUN_LOCAL_WINDOWS;
index
});
let window = &mut local.run_windows[index];
if same.is_none() && window.cached.is_some() {
let released = window.release();
self.inner
.stats
.run_local_window_releases
.fetch_add(released as u64, Ordering::Relaxed);
}
debug_assert!(window.next >= window.end);
window.cached = Some(cached.clone());
window.extent_size = extent_size;
window.next = next;
window.end = end;
window.target = window
.target
.min(self.inner.config.run_local_window_capacity as u32)
.max(
INITIAL_RUN_LOCAL_WINDOW_TARGET
.min(self.inner.config.run_local_window_capacity as u32),
);
self.inner
.stats
.run_local_window_refills
.fetch_add(1, Ordering::Relaxed);
}
fn try_reuse_cached_run(
&self,
layout: Layout,
extent_size: usize,
dedicated: bool,
owner: u64,
) -> Result<Option<(SpanHandle, usize, usize)>, BoAllocError> {
self.with_local_cache(|local| {
if !dedicated {
if let Some(allocation) = self.try_allocate_run_window(local, layout, extent_size) {
return Ok(Some(allocation));
}
}
let len = if dedicated {
local.dedicated_run_len
} else {
local.run_len
};
if len == 0 {
return Ok(None);
}
let start = if dedicated {
local.dedicated_run_cursor
} else {
local.run_cursor
};
let mut attempted = [false; RECENT_DEDICATED_RUNS];
for offset in 0..len {
let index = if dedicated {
let Some(index) =
(0..len)
.filter(|index| !attempted[*index])
.min_by_key(|index| {
let entry = local.dedicated_runs[*index]
.as_ref()
.expect("the live dedicated cache prefix is populated");
(
usize::from(entry.span.size < extent_size),
entry.span.size,
(*index + len - start) % len,
)
})
else {
break;
};
attempted[index] = true;
index
} else {
(start + offset) % len
};
let entry = if dedicated {
local.dedicated_runs[index].as_ref()
} else {
local.runs[index].as_ref()
};
let Some(entry) = entry.cloned() else {
continue;
};
let span = &*entry.span;
if span.generation.load(Ordering::Acquire) != entry.generation
|| (!span.is_run_territory() && span.owner.load(Ordering::Acquire) != owner)
{
continue;
}
let batch_capacity = if span.is_run_territory() && !dedicated {
self.run_window_target(local, &entry, extent_size)
} else {
1
};
if let Some(prepared) = self.try_prepare_run(
span,
layout,
extent_size,
dedicated,
owner,
batch_capacity,
)? {
let refreshed = CachedSpan {
span: entry.span.clone(),
generation: if prepared.activated {
span.generation.load(Ordering::Acquire)
} else {
entry.generation
},
};
if dedicated {
local.dedicated_runs[index] = Some(refreshed);
local.dedicated_run_cursor = (index + 1) % len;
} else {
local.runs[index] = Some(refreshed);
local.run_cursor = (index + 1) % len;
}
if let Some((next, end)) = prepared.reservation {
self.install_run_window(local, &entry, extent_size, next, end);
}
return Ok(Some((entry.span, prepared.user, prepared.usable)));
}
}
Ok(None)
})
}
fn try_reuse_run_snapshot(
&self,
layout: Layout,
extent_size: usize,
dedicated: bool,
owner: u64,
) -> Result<Option<(SpanHandle, usize, usize)>, BoAllocError> {
self.with_topology_snapshot(|snapshot| {
for owner_class in 0..3 {
if dedicated {
let candidate = snapshot
.run_spans(true)
.iter()
.filter(|span| {
let current_owner = span.owner.load(Ordering::Acquire);
let class = if current_owner == owner {
0
} else if current_owner == 0 {
1
} else {
2
};
class == owner_class && span.size >= extent_size && span.live() == 0
})
.min_by_key(|span| span.size)
.cloned();
let Some(span) = candidate else {
continue;
};
if self.try_claim_run_owner(&span, owner, owner_class == 2) {
if let Some(prepared) =
self.try_prepare_run(&span, layout, extent_size, true, owner, 1)?
{
return Ok(Some((span, prepared.user, prepared.usable)));
}
}
continue;
}
for span in snapshot.run_spans(dedicated) {
let current_owner = span.owner.load(Ordering::Acquire);
let class = if current_owner == owner {
0
} else if current_owner == 0 {
1
} else {
2
};
if class != owner_class
|| !self.try_claim_run_owner(span, owner, owner_class == 2)
{
continue;
}
if let Some(prepared) =
self.try_prepare_run(span, layout, extent_size, dedicated, owner, 1)?
{
return Ok(Some((span.clone(), prepared.user, prepared.usable)));
}
}
}
Ok(None)
})
}
fn try_prepare_run(
&self,
span: &SpanDesc,
layout: Layout,
extent_size: usize,
dedicated: bool,
owner: u64,
batch_capacity: u32,
) -> Result<Option<PreparedRun>, BoAllocError> {
let expected_kind = if dedicated {
SpanKind::Dedicated
} else {
SpanKind::Run
};
let kind = span.kind();
if kind == SpanKind::Run && !dedicated && span.is_run_territory() {
if span.run_extent_size() != Some(extent_size) {
return Ok(None);
}
let Some(allocation) =
span.try_allocate_run_territory_batch(layout, batch_capacity, |base, size| {
unsafe { self.inner.backing.commit(base, size) }
})?
else {
return Ok(None);
};
if allocation.newly_committed != 0 {
let committed_bytes = allocation.newly_committed as usize * extent_size;
self.inner
.stats
.committed
.fetch_add(committed_bytes, Ordering::Relaxed);
self.inner
.stats
.reserved_run_activations
.fetch_add(allocation.newly_committed as u64, Ordering::Relaxed);
let extension_start = allocation.index.max(INITIAL_RUN_TERRITORY_EXTENTS as u32);
let extension_end = allocation.reserved_end;
if extension_end > extension_start {
self.inner
.stats
.run_territory_extension_extents
.fetch_add((extension_end - extension_start) as u64, Ordering::Relaxed);
if allocation.index <= INITIAL_RUN_TERRITORY_EXTENTS as u32
&& extension_end > INITIAL_RUN_TERRITORY_EXTENTS as u32
{
self.inner
.stats
.run_territory_extensions
.fetch_add(1, Ordering::Relaxed);
}
}
}
let reservation = (allocation.reserved_end > allocation.index + 1)
.then_some((allocation.index + 1, allocation.reserved_end));
return Ok(Some(PreparedRun {
user: allocation.user,
usable: allocation.usable,
activated: false,
reservation,
}));
}
if span.size < extent_size || span.live() != 0 {
return Ok(None);
}
let Some(user) = align_up(span.base + size_of::<RunHeader>(), layout.align()) else {
return Ok(None);
};
let usable = span.base + span.size - user;
if user
.checked_add(layout.size())
.is_none_or(|end| end > span.base + span.size)
{
return Ok(None);
}
if kind == expected_kind {
if !span.try_account_run_allocation(layout.size(), usable) {
return Ok(None);
}
if dedicated && span.take_empty_dedicated_commit_charge() {
let previous = self
.inner
.empty_dedicated_committed
.fetch_sub(span.size, Ordering::Relaxed);
debug_assert!(previous >= span.size);
}
return Ok(Some(PreparedRun {
user,
usable,
activated: false,
reservation: None,
}));
}
if dedicated && kind == SpanKind::DedicatedReserved {
if !span.try_freeze_reserved_dedicated() {
return Ok(None);
}
span.activate_reserved_dedicated_with_first_allocation(layout.size(), usable);
self.inner
.stats
.reserved_run_activations
.fetch_add(1, Ordering::Relaxed);
return Ok(Some(PreparedRun {
user,
usable,
activated: true,
reservation: None,
}));
}
if dedicated
|| kind != SpanKind::ReservedRun
|| span.owner.load(Ordering::Acquire) != owner
|| !span.try_freeze_reserved_run(owner)
{
return Ok(None);
}
if let Err(error) = unsafe { self.inner.backing.commit(span.base, span.size) } {
span.unfreeze();
return Err(error);
}
span.advance_reserved_run_generation();
span.activate_reserved_run_with_first_allocation(layout.size(), usable);
self.inner
.stats
.committed
.fetch_add(span.size, Ordering::Relaxed);
self.inner
.stats
.reserved_run_activations
.fetch_add(1, Ordering::Relaxed);
Ok(Some(PreparedRun {
user,
usable,
activated: true,
reservation: None,
}))
}
fn try_claim_run_owner(&self, span: &SpanDesc, owner: u64, allow_steal: bool) -> bool {
let current = span.owner.load(Ordering::Acquire);
if span.is_run_territory() {
return true;
}
if current == owner {
return true;
}
if current == 0 {
return span
.owner
.compare_exchange(0, owner, Ordering::AcqRel, Ordering::Acquire)
.is_ok();
}
if !allow_steal
|| span.record_foreign_miss() < self.inner.config.red_cold_slow_paths
|| !span.try_freeze_empty()
{
return false;
}
let transferred = span.kind() != SpanKind::Retired
&& span.owner.load(Ordering::Acquire) == current
&& span
.owner
.compare_exchange(current, owner, Ordering::AcqRel, Ordering::Acquire)
.is_ok();
if transferred {
span.generation.fetch_add(1, Ordering::AcqRel);
self.inner.stats.steals.fetch_add(1, Ordering::Relaxed);
}
span.unfreeze();
transferred
}
fn finish_run_allocation(
&self,
span: &SpanDesc,
user: usize,
usable: usize,
) -> Result<NonNull<[u8]>, BoAllocError> {
let header = size_of::<RunHeader>();
let generation = span.generation.load(Ordering::Relaxed);
let run_header = RunHeader {
magic: RUN_MAGIC,
allocator_id: self.inner.id,
descriptor: span as *const SpanDesc,
generation,
};
unsafe { std::ptr::write((user - header) as *mut RunHeader, run_header) };
self.finish_allocation(user, usable)
}
fn finish_allocation(
&self,
address: usize,
usable: usize,
) -> Result<NonNull<[u8]>, BoAllocError> {
let pointer = NonNull::new(address as *mut u8).ok_or(BoAllocError::OutOfMemory)?;
Ok(NonNull::slice_from_raw_parts(pointer, usable))
}
#[inline]
pub unsafe fn deallocate(&self, pointer: NonNull<u8>, layout: Layout) {
if layout.size() == 0 {
return;
}
let address = pointer.as_ptr() as usize;
if let Some(class_index) = self.inner.config.class_for(layout.size(), layout.align()) {
let base = address & !(SMALL_SPAN_SIZE - 1);
let last = last_local_cache();
let last =
(last.allocator_id == self.inner.id && !last.pointer.is_null()).then_some(last);
if let Some(last) = last {
if self.try_deallocate_black_leased(last, address, layout, class_index, base) {
return;
}
}
unsafe { self.deallocate_small_slow(address, layout, class_index, base, last) };
} else {
unsafe { self.deallocate_run_slow(address, layout) };
}
}
#[inline(never)]
unsafe fn deallocate_small_slow(
&self,
address: usize,
layout: Layout,
class_index: usize,
base: usize,
last: Option<LastLocalCache>,
) {
if headerless_small_class_for_size(layout.size()).is_some() {
if let Some(descriptor) =
self.try_resolve_headerless_cached_span(last, class_index, base)
{
let span = unsafe { &*descriptor };
unsafe { self.deallocate_small_resolved(span, address, layout, class_index, last) };
return;
}
let Some(span) = self.inner.address_tree.get(base) else {
debug_assert!(false, "live headerless small span is absent from the tree");
return;
};
unsafe { self.deallocate_small_resolved(&span, address, layout, class_index, last) };
return;
}
let anchor = unsafe { &*(base as *const SpanAnchor) };
debug_assert_eq!(anchor.magic, ANCHOR_MAGIC, "invalid small-span anchor");
debug_assert_eq!(
anchor.allocator_id, self.inner.id,
"pointer belongs to another allocator"
);
if anchor.magic != ANCHOR_MAGIC || anchor.allocator_id != self.inner.id {
return;
}
let span = unsafe { &*anchor.descriptor };
debug_assert_eq!(
anchor.class_index as usize, class_index,
"deallocation layout maps to a different size class"
);
unsafe { self.deallocate_small_resolved(span, address, layout, class_index, last) };
}
#[inline(never)]
unsafe fn deallocate_run_slow(&self, address: usize, layout: Layout) {
let header_address = address - size_of::<RunHeader>();
let header = unsafe { &*(header_address as *const RunHeader) };
debug_assert_eq!(header.magic, RUN_MAGIC, "invalid run header");
debug_assert_eq!(
header.allocator_id, self.inner.id,
"pointer belongs to another allocator"
);
if header.magic != RUN_MAGIC || header.allocator_id != self.inner.id {
return;
}
let span = unsafe { &*header.descriptor };
debug_assert_eq!(span.generation.load(Ordering::Acquire), header.generation);
if span.deallocate_run(address, layout) && span.kind() == SpanKind::Dedicated {
self.publish_empty_dedicated_commit(span);
}
}
fn publish_empty_dedicated_commit(&self, span: &SpanDesc) {
let epoch = self
.inner
.dedicated_retention_epoch
.fetch_add(1, Ordering::Relaxed)
.wrapping_add(1);
let previous = self
.inner
.empty_dedicated_committed
.fetch_add(span.size, Ordering::AcqRel);
if !span.publish_empty_dedicated_commit_charge(epoch) {
let charged = self
.inner
.empty_dedicated_committed
.fetch_sub(span.size, Ordering::AcqRel);
debug_assert!(charged >= span.size);
return;
}
if previous.saturating_add(span.size) > self.inner.config.dedicated_commit_cache_bytes {
self.evict_cold_dedicated_commits();
}
}
fn evict_cold_dedicated_commits(&self) {
let budget = self.inner.config.dedicated_commit_cache_bytes;
let mut skipped = [0; 4];
let mut skipped_len = 0;
while self.inner.empty_dedicated_committed.load(Ordering::Acquire) > budget {
let candidate = self
.inner
.address_tree
.values()
.into_iter()
.filter(|span| {
span.kind() == SpanKind::Dedicated
&& span.live() == 0
&& !skipped[..skipped_len].contains(&span.base)
})
.filter_map(|span| {
span.empty_dedicated_commit_epoch()
.map(|epoch| (epoch, span))
})
.min_by_key(|(epoch, _)| *epoch)
.map(|(_, span)| span);
let Some(candidate) = candidate else {
return;
};
if self.try_discard_empty_dedicated(&candidate) {
skipped_len = 0;
} else if skipped_len == skipped.len() {
return;
} else {
skipped[skipped_len] = candidate.base;
skipped_len += 1;
}
}
}
fn try_discard_empty_dedicated(&self, span: &SpanDesc) -> bool {
if span.kind() != SpanKind::Dedicated
|| !span.has_empty_dedicated_commit_charge()
|| !span.try_freeze_empty()
{
return false;
}
if span.kind() != SpanKind::Dedicated
|| span.live() != 0
|| !span.has_empty_dedicated_commit_charge()
{
span.unfreeze();
return false;
}
if unsafe { self.inner.backing.discard(span.base, span.size) }.is_err() {
span.unfreeze();
return false;
}
span.finish_dedicated_discard();
let previous = self
.inner
.empty_dedicated_committed
.fetch_sub(span.size, Ordering::AcqRel);
debug_assert!(previous >= span.size);
self.inner.stats.discards.fetch_add(1, Ordering::Relaxed);
true
}
#[inline]
fn try_deallocate_black_leased(
&self,
last: LastLocalCache,
address: usize,
layout: Layout,
class_index: usize,
base: usize,
) -> bool {
if self.inner.config.local_magazine_capacity == 0 {
return false;
}
let local = unsafe { &mut *last.pointer };
#[cfg(debug_assertions)]
if local.active.replace(true) {
return false;
}
let _access = LocalCacheAccess {
#[cfg(debug_assertions)]
active: &local.active,
};
let class = &mut local.classes[class_index];
if class.magazine.leased && !class.magazine.pointer.is_null() {
let pointer = class.magazine.pointer;
let span = unsafe { &*pointer };
if span.base == base {
let generation = class.magazine.generation;
unsafe {
self.deallocate_to_leased_magazine(
class,
span,
address,
layout,
class_index,
last.owner,
generation,
)
};
return true;
}
}
let Some(entry) = class.black_ring.find_by_base_mut(base) else {
return false;
};
let span = unsafe { &*entry.pointer };
let cached_address = unsafe {
span.deallocate_small_to_local_cache(address, last.owner, entry.generation, class_index)
};
unsafe { entry.push(cached_address, layout) };
true
}
#[inline]
fn try_resolve_headerless_cached_span(
&self,
last: Option<LastLocalCache>,
class_index: usize,
base: usize,
) -> Option<*const SpanDesc> {
let last = last?;
let epoch = self.inner.trim_epoch.load(Ordering::Acquire);
let local = unsafe { &*last.pointer };
if local.trim_epoch != epoch {
return None;
}
#[cfg(debug_assertions)]
if local.active.get() {
return None;
}
let class = &local.classes[class_index];
if class.magazine.leased {
let pointer = class.magazine.pointer;
if !pointer.is_null() && unsafe { (*pointer).base == base } {
return Some(pointer);
}
}
if let Some(pointer) = class.recent[..self.inner.config.recent_spans_per_class]
.iter()
.flatten()
.find_map(|cached| {
(cached.span.base == base && cached.span.kind() == SpanKind::Small)
.then_some(cached.pointer())
})
{
return Some(pointer);
}
let cache_index = territory_cache_index(class_index)?;
let cache = &local.low_capacity_territories[cache_index];
let cached = cache.get_by_base(base)?;
(cached.span.kind() == SpanKind::Small && cached.span.class_index() == Some(class_index))
.then_some(cached.pointer())
}
#[inline]
unsafe fn deallocate_small_resolved(
&self,
span: &SpanDesc,
address: usize,
layout: Layout,
class_index: usize,
last: Option<LastLocalCache>,
) {
debug_assert_eq!(span.class_index(), Some(class_index));
debug_assert_eq!(span.base, address & !(SMALL_SPAN_SIZE - 1));
if let Some(last) = last {
if self.inner.config.local_magazine_capacity != 0
&& self.try_deallocate_to_local_magazine(last, span, address, layout, class_index)
{
return;
}
}
if self.inner.config.remote_cache_capacity != 0 && thread_cache_available() {
let foreign_owner =
last.is_none_or(|last| span.owner.load(Ordering::Acquire) != last.owner);
if foreign_owner {
self.cache_remote_free(span, address, layout, class_index);
return;
}
}
let released = unsafe {
span.deallocate_small(
address,
layout,
last.map(|last| last.owner),
self.inner.config.remote_free_batching,
self.inner.config.recent_free_word_hints,
)
};
debug_assert!(
released.is_some(),
"valid small deallocation could not enter or validate its descriptor"
);
}
pub fn trim(&self, mode: TrimMode) -> TrimStats {
if mode == TrimMode::Aggressive {
let epoch = self.inner.trim_epoch.fetch_add(1, Ordering::AcqRel) + 1;
self.refresh_current_local_cache(epoch);
}
let mut result = TrimStats::default();
let mut topology = self.inner.topology.write().expect("topology lock poisoned");
let _maintenance = self.begin_maintenance();
let targets: Vec<_> = topology
.tree
.values()
.into_iter()
.filter(|span| {
span.live() == 0
&& matches!(
span.kind(),
SpanKind::Small
| SpanKind::ReservedSmall
| SpanKind::ReservedRun
| SpanKind::Run
| SpanKind::Dedicated
| SpanKind::DedicatedReserved
)
&& (mode == TrimMode::Aggressive || span.owner.load(Ordering::Acquire) == 0)
})
.collect();
let mut reclaimed_extents = Vec::with_capacity(targets.len());
let mut target_index = 0;
while target_index < targets.len() {
let span = &targets[target_index];
if matches!(span.kind(), SpanKind::Small | SpanKind::Run) {
if !span.try_freeze_empty() {
target_index += 1;
continue;
}
let mut group_end = target_index + 1;
while group_end < targets.len() {
let previous = &targets[group_end - 1];
let next = &targets[group_end];
if !matches!(next.kind(), SpanKind::Small | SpanKind::Run)
|| next.chunk_base != span.chunk_base
|| previous.base + previous.size != next.base
|| !next.try_freeze_empty()
{
break;
}
group_end += 1;
}
let group = &targets[target_index..group_end];
let last = group
.last()
.expect("decommit group contains its first span");
let decommit_size = last.base + last.size - span.base;
let committed_size = group
.iter()
.map(|member| member.committed_bytes())
.sum::<usize>();
if unsafe { self.inner.backing.decommit(span.base, decommit_size) }.is_err() {
for member in group {
member.unfreeze();
}
target_index = group_end;
continue;
}
for member in group {
let removed = topology.tree.remove(member.base);
assert!(
removed.is_some(),
"frozen trim target must remain reachable"
);
member.retire();
reclaimed_extents.push((member.base, member.size, member.chunk_base));
}
self.inner
.stats
.committed
.fetch_sub(committed_size, Ordering::Relaxed);
self.inner.stats.decommits.fetch_add(1, Ordering::Relaxed);
result.spans_reclaimed += group.len();
result.bytes_decommitted += committed_size;
target_index = group_end;
continue;
}
if !span.try_freeze_empty() {
target_index += 1;
continue;
}
match span.kind() {
SpanKind::Dedicated => {
if !span.has_empty_dedicated_commit_charge() {
span.unfreeze();
target_index += 1;
continue;
}
if unsafe { self.inner.backing.release(span.base, span.size) }.is_ok() {
if topology.tree.remove(span.base).is_some() {
if span.take_empty_dedicated_commit_charge() {
let previous = self
.inner
.empty_dedicated_committed
.fetch_sub(span.size, Ordering::AcqRel);
debug_assert!(previous >= span.size);
}
self.inner
.stats
.reserved
.fetch_sub(span.size, Ordering::Relaxed);
self.inner
.stats
.committed
.fetch_sub(span.size, Ordering::Relaxed);
result.chunks_released += 1;
result.bytes_released += span.size;
self.inner
.stats
.chunk_releases
.fetch_add(1, Ordering::Relaxed);
span.retire();
}
} else {
span.unfreeze();
}
}
SpanKind::DedicatedReserved => {
if unsafe { self.inner.backing.release(span.base, span.size) }.is_ok() {
if topology.tree.remove(span.base).is_some() {
self.inner
.stats
.reserved
.fetch_sub(span.size, Ordering::Relaxed);
self.inner
.stats
.committed
.fetch_sub(span.size, Ordering::Relaxed);
result.chunks_released += 1;
result.bytes_released += span.size;
self.inner
.stats
.chunk_releases
.fetch_add(1, Ordering::Relaxed);
span.retire();
}
} else {
span.unfreeze();
}
}
SpanKind::ReservedSmall | SpanKind::ReservedRun => {
let removed = topology.tree.remove(span.base);
assert!(
removed.is_some(),
"frozen trim target must remain reachable"
);
span.retire();
reclaimed_extents.push((span.base, span.size, span.chunk_base));
result.spans_reclaimed += 1;
}
_ => span.unfreeze(),
}
target_index += 1;
}
self.insert_reclaimed_free_spans(&mut topology, &reclaimed_extents);
self.merge_free_spans(&mut topology);
if mode == TrimMode::Aggressive {
self.release_empty_chunks(&mut topology, &mut result);
}
self.publish_topology_snapshot(&topology);
result
}
fn insert_reclaimed_free_spans(
&self,
topology: &mut Topology,
reclaimed: &[(usize, usize, usize)],
) {
let Some(&(mut base, first_size, mut chunk_base)) = reclaimed.first() else {
return;
};
let mut end = base + first_size;
for &(next_base, next_size, next_chunk_base) in &reclaimed[1..] {
if next_chunk_base == chunk_base && next_base == end {
end += next_size;
continue;
}
let free = topology
.tree
.allocate_span(SpanDesc::free(base, end - base, chunk_base));
topology.tree.insert(base, free);
self.inner.free_extent_hint.store(base, Ordering::Release);
base = next_base;
end = next_base + next_size;
chunk_base = next_chunk_base;
}
let free = topology
.tree
.allocate_span(SpanDesc::free(base, end - base, chunk_base));
topology.tree.insert(base, free);
self.inner.free_extent_hint.store(base, Ordering::Release);
}
fn merge_free_spans(&self, topology: &mut Topology) {
let spans = topology.tree.values();
let mut start = 0;
while start < spans.len() {
if spans[start].kind() != SpanKind::Free {
start += 1;
continue;
}
let mut end = start + 1;
while end < spans.len()
&& spans[end].kind() == SpanKind::Free
&& spans[end].chunk_base == spans[start].chunk_base
&& spans[end - 1].base + spans[end - 1].size == spans[end].base
{
end += 1;
}
if end - start == 1 {
start = end;
continue;
}
let base = spans[start].base;
let chunk_base = spans[start].chunk_base;
let size = spans[end - 1].base + spans[end - 1].size - base;
for span in &spans[start..end] {
let removed = topology.tree.remove(span.base);
debug_assert!(removed.is_some());
span.retire();
}
let merged = topology
.tree
.allocate_span(SpanDesc::free(base, size, chunk_base));
topology.tree.insert(base, merged);
self.inner.free_extent_hint.store(base, Ordering::Release);
self.inner
.stats
.merges
.fetch_add((end - start - 1) as u64, Ordering::Relaxed);
start = end;
}
}
fn release_empty_chunks(&self, topology: &mut Topology, result: &mut TrimStats) {
let mut retained = Vec::with_capacity(topology.chunks.len());
for chunk in topology.chunks.drain(..) {
let fully_free = topology
.tree
.get(chunk.base)
.is_some_and(|span| span.kind() == SpanKind::Free && span.size == chunk.size);
if fully_free {
if unsafe { self.inner.backing.release(chunk.base, chunk.size) }.is_ok() {
if let Some(span) = topology.tree.remove(chunk.base) {
span.retire();
self.inner
.stats
.reserved
.fetch_sub(chunk.size, Ordering::Relaxed);
self.inner
.stats
.chunk_releases
.fetch_add(1, Ordering::Relaxed);
result.chunks_released += 1;
result.bytes_released += chunk.size;
}
} else {
retained.push(chunk);
}
} else {
retained.push(chunk);
}
}
topology.chunks = retained;
}
pub fn stats(&self) -> StatsSnapshot {
self.synchronize_current_black_accounting();
let mut result = self.inner.stats.snapshot();
result.empty_dedicated_committed_bytes =
self.inner.empty_dedicated_committed.load(Ordering::Acquire);
result.metadata_bytes = self.inner.address_tree.metadata_bytes();
let tree_operations = self.inner.address_tree.operation_stats();
result.tree_root_replacements = tree_operations.root_replacements;
result.tree_root_collapses = tree_operations.root_collapses;
result.tree_leaf_splits = tree_operations.leaf_splits;
result.tree_parent_inserts = tree_operations.parent_inserts;
result.tree_internal_splits = tree_operations.internal_splits;
result.tree_logical_removes = tree_operations.logical_removes;
result.tree_leaf_upserts = tree_operations.leaf_upserts;
result.tree_redirects = tree_operations.redirects;
result.tree_cross_parent_redirects = tree_operations.cross_parent_redirects;
result.tree_internal_redirects = tree_operations.internal_redirects;
result.tree_internal_redistributions = tree_operations.internal_redistributions;
result.tree_parent_cleanups = tree_operations.parent_cleanups;
result.tree_batch_replacements = tree_operations.batch_replacements;
result.tree_help_calls = tree_operations.help_calls;
result.tree_operation_aborts = tree_operations.aborts;
result.tree_candidate_discards = tree_operations.candidate_discards;
result.tree_node_slots = tree_operations.node_slots;
result.tree_live_nodes = tree_operations.live_nodes;
result.tree_retired_nodes = tree_operations.retired_nodes;
result.tree_reused_nodes = tree_operations.reused_nodes;
result.tree_node_object_slots = tree_operations.node_object_slots;
result.tree_live_node_objects = tree_operations.live_node_objects;
result.tree_reused_node_objects = tree_operations.reused_node_objects;
result.span_descriptor_slots = tree_operations.span_slots;
result.live_span_descriptors = tree_operations.live_spans;
result.reused_span_descriptors = tree_operations.reused_spans;
result.bitmap_slots = tree_operations.bitmap_slots;
result.live_bitmaps = tree_operations.live_bitmaps;
result.reused_bitmaps = tree_operations.reused_bitmaps;
result.payload_vector_slots = tree_operations.payload_vector_slots;
result.live_payload_vectors = tree_operations.live_payload_vectors;
result.reused_payload_vectors = tree_operations.reused_payload_vectors;
result.tree_metadata_blocks = tree_operations.metadata_blocks;
result.tree_metadata_reserved_bytes = tree_operations.metadata_reserved_bytes;
let spans = self.inner.address_tree.values();
result.requested_live_bytes = spans.iter().map(|span| span.requested_live()).sum();
result.usable_live_bytes = spans.iter().map(|span| span.usable_live()).sum();
for span in spans {
match span.kind() {
SpanKind::Free => {
if span.owner.load(Ordering::Relaxed) == 0 {
result.white_spans += 1;
} else {
result.green_spans += 1;
result.local_free_spans += 1;
}
}
SpanKind::Small => {
result.black_spans += 1;
if span.live() == 0 && span.owner.load(Ordering::Relaxed) != 0 {
result.empty_black_spans += 1;
}
if span.is_cohort_sealed() {
result.sealed_black_spans += 1;
let class_size = SIZE_CLASSES
[span.class_index().expect("a small span has a size class")];
result.sealed_hole_bytes +=
(span.capacity() - span.live()) as usize * class_size;
} else if span.cohort_epoch() != 0 && span.owner.load(Ordering::Relaxed) != 0 {
result.young_spans += 1;
}
}
SpanKind::ReservedSmall | SpanKind::ReservedRun => {
if span.owner.load(Ordering::Relaxed) == 0 {
result.white_spans += 1;
} else if span.foreign_misses() >= self.inner.config.red_cold_slow_paths {
result.red_spans += 1;
} else {
result.green_spans += 1;
result.local_free_spans += 1;
}
}
SpanKind::Run | SpanKind::Dedicated | SpanKind::DedicatedReserved => {
if span.kind() == SpanKind::DedicatedReserved {
result.discarded_bytes += span.size;
}
if span.live() == 0 {
result.white_spans += 1
} else {
result.black_spans += 1
}
}
SpanKind::Retired => {}
}
}
result
}
pub fn validate(&self) -> Result<(), InvariantError> {
self.synchronize_current_black_accounting();
let topology = self.inner.topology.write().expect("topology lock poisoned");
let _maintenance = self.begin_maintenance();
topology.tree.validate()?;
let spans = topology.tree.values();
for span in &spans {
if span.is_run_territory() {
let live = span.live();
let high_water = span.run_high_water();
let extent_size = span
.run_extent_size()
.ok_or_else(|| InvariantError::new("run territory has no extent stride"))?;
if extent_size == 0
|| span.size != extent_size.saturating_mul(span.capacity() as usize)
|| high_water > span.capacity()
|| live > high_water
{
return Err(InvariantError::new(
"run territory capacity, high-water, or live accounting is invalid",
));
}
}
if span.is_cohort_sealed()
&& (span.cohort_epoch() == 0
|| span.kind() != SpanKind::Small
|| span
.class_index()
.is_none_or(|class_index| SIZE_CLASSES[class_index] > 4096))
{
return Err(InvariantError::new(
"sealed cohort metadata is inconsistent with its small span",
));
}
}
for chunk in &topology.chunks {
let mut in_chunk: Vec<_> = spans
.iter()
.filter(|span| {
span.chunk_base == chunk.base
&& !matches!(
span.kind(),
SpanKind::Dedicated | SpanKind::DedicatedReserved
)
})
.collect();
in_chunk.sort_by_key(|span| span.base);
let mut cursor = chunk.base;
for span in in_chunk {
if span.base != cursor {
return Err(InvariantError::new(
"chunk span partition contains a gap or overlap",
));
}
cursor = cursor
.checked_add(span.size)
.ok_or_else(|| InvariantError::new("chunk end overflows"))?;
}
if cursor != chunk.base + chunk.size {
return Err(InvariantError::new(
"chunk span partition does not cover the reservation",
));
}
}
Ok(())
}
fn publish_topology_snapshot(&self, topology: &Topology) {
self.publish_snapshot(TopologyReadSnapshot::from_topology(topology));
}
fn synchronize_current_black_accounting(&self) {
LAST_LOCAL_CACHE.with(|last_cache| {
let last = last_cache.get();
if last.allocator_id != self.inner.id || last.pointer.is_null() {
return;
}
let local = unsafe { &mut *last.pointer };
for (class_index, class) in local.classes.iter_mut().enumerate() {
unsafe { class.remote.flush(class_index) };
if !class.magazine.leased || class.magazine.pointer.is_null() {
class.black_ring.fold_accounting();
continue;
}
let span = unsafe { &*class.magazine.pointer };
class.magazine.fold_accounting(span);
class.black_ring.fold_accounting();
}
});
}
fn flush_current_remote_caches(&self) {
LAST_LOCAL_CACHE.with(|last_cache| {
let last = last_cache.get();
if last.allocator_id != self.inner.id || last.pointer.is_null() {
return;
}
let local = unsafe { &mut *last.pointer };
for (class_index, class) in local.classes.iter_mut().enumerate() {
unsafe { class.remote.flush(class_index) };
}
});
}
fn cache_remote_free(
&self,
span: &SpanDesc,
address: usize,
layout: Layout,
class_index: usize,
) {
self.with_local_cache(|local| {
unsafe {
local.classes[class_index].remote.push(
span,
address,
layout,
class_index,
self.inner.config.remote_cache_capacity,
)
};
});
}
fn publish_address_tree_snapshot(&self) {
self.publish_snapshot(TopologyReadSnapshot::from_tree(&self.inner.address_tree));
}
fn publish_snapshot(&self, snapshot: TopologyReadSnapshot) {
let handle = self.inner.collector.register();
let guard = handle.pin();
let replacement = Owned::new(snapshot);
let previous = self
.inner
.topology_snapshot
.swap(replacement, Ordering::AcqRel, &guard);
if !previous.is_null() {
unsafe { guard.defer_destroy(previous) };
}
guard.flush();
self.inner
.stats
.topology_snapshot_publishes
.fetch_add(1, Ordering::Relaxed);
}
fn cache_span(&self, class_index: usize, span: &SpanHandle) {
self.cache_raw_span(
class_index,
CachedSpan {
span: span.clone(),
generation: span.generation.load(Ordering::Acquire),
},
);
}
fn remember_primary_territory(&self, class_index: usize) {
self.with_local_cache(|local| {
let class = &mut local.classes[class_index];
let Some(primary) = class.recent[0].as_ref() else {
return;
};
if class
.territory_return
.as_ref()
.is_some_and(|cached| cached.pointer() == primary.pointer())
{
return;
}
class.territory_return = Some(primary.clone());
});
}
fn cache_returned_territory(&self, class_index: usize, cached: CachedSpan) {
self.with_local_cache(|local| {
let return_pointer = cached.pointer();
let next_return = local.classes[class_index].recent[0]
.as_ref()
.filter(|primary| primary.pointer() != return_pointer)
.cloned();
if let Some(next_return) = next_return {
local.classes[class_index].territory_return = Some(next_return);
}
self.cache_raw_span_in_local(local, class_index, cached);
});
}
fn cache_run(&self, dedicated: bool, span: &SpanHandle) {
self.cache_raw_run(
dedicated,
CachedSpan {
span: span.clone(),
generation: span.generation.load(Ordering::Acquire),
},
);
}
fn prefer_cached_run(&self, span: &SpanHandle) {
self.with_local_cache(|local| {
if let Some(index) = local.runs.iter().position(|entry| {
entry
.as_ref()
.is_some_and(|entry| entry.pointer() == span.as_ptr())
}) {
local.run_cursor = index;
}
});
}
fn cache_raw_run(&self, dedicated: bool, cached: CachedSpan) {
self.with_local_cache(|local| {
let existing = if dedicated {
local.dedicated_runs.iter().position(|entry| {
entry
.as_ref()
.is_some_and(|entry| entry.pointer() == cached.pointer())
})
} else {
local.runs.iter().position(|entry| {
entry
.as_ref()
.is_some_and(|entry| entry.pointer() == cached.pointer())
})
};
if let Some(index) = existing {
if dedicated {
local.dedicated_runs[index] = Some(cached);
} else {
local.runs[index] = Some(cached);
}
return;
}
let (index, evicted) = if dedicated {
if local.dedicated_run_len < RECENT_DEDICATED_RUNS {
let index = local.dedicated_run_len;
local.dedicated_run_len += 1;
local.dedicated_runs[index] = Some(cached);
(index, None)
} else {
let index = local.dedicated_run_cursor;
let evicted = local.dedicated_runs[index].replace(cached);
(index, evicted)
}
} else if local.run_len < RECENT_RUNS {
let index = local.run_len;
local.run_len += 1;
local.runs[index] = Some(cached);
(index, None)
} else {
let index = local.run_cursor;
let evicted = local.runs[index].replace(cached);
(index, evicted)
};
if dedicated {
local.dedicated_run_cursor = (index + 1) % local.dedicated_run_len;
} else {
local.run_cursor = (index + 1) % local.run_len;
}
if let Some(evicted) = evicted {
let _ = evicted.span.owner.compare_exchange(
local.owner,
0,
Ordering::AcqRel,
Ordering::Acquire,
);
}
});
}
fn cache_raw_span(&self, class_index: usize, cached: CachedSpan) {
self.with_local_cache(|local| {
self.cache_raw_span_in_local(local, class_index, cached);
});
}
fn cache_raw_span_in_local(
&self,
local: &mut LocalCache,
class_index: usize,
cached: CachedSpan,
) {
let owner = local.owner;
let class = &mut local.classes[class_index];
let limit = self.inner.config.recent_spans_per_class;
let cohort_limit = self.cohort_limit(class_index);
if let Some(position) = class.recent[..limit].iter().position(|entry| {
entry
.as_ref()
.is_some_and(|entry| entry.pointer() == cached.pointer())
}) {
if cohort_limit != 0 && cached.span.cohort_epoch() == 0 {
class.cohort_epoch = next_cohort_epoch(class.cohort_epoch);
let _ =
cached
.span
.begin_small_cohort(owner, cached.generation, class.cohort_epoch);
}
class.recent[position] = Some(cached);
class.recent[..=position].rotate_right(1);
return;
}
if cohort_limit != 0 {
class.cohort_epoch = next_cohort_epoch(class.cohort_epoch);
let _ = cached
.span
.begin_small_cohort(owner, cached.generation, class.cohort_epoch);
}
let evicted = class.recent[limit - 1].take();
class.recent[..limit].rotate_right(1);
class.recent[0] = Some(cached);
if cohort_limit == 0 {
if let Some(previous) = evicted {
if class.magazine.pointer == previous.pointer() {
class
.magazine
.flush(self.inner.config.recent_free_word_hints);
}
let previous = &*previous.span;
if previous.live() == 0 {
let _ = previous.owner.compare_exchange(
owner,
0,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
return;
}
let retiring = if cohort_limit < limit {
class.recent[cohort_limit].clone()
} else {
evicted
};
if let Some(previous) = retiring {
if class.magazine.pointer == previous.pointer() {
class
.magazine
.flush(self.inner.config.recent_free_word_hints);
}
let previous = &*previous.span;
if previous.live() == 0 {
if previous.try_recycle_empty_cohort(owner) {
self.inner
.stats
.cohort_recycles
.fetch_add(1, Ordering::Relaxed);
}
} else if previous.seal_small_cohort(owner, previous.generation.load(Ordering::Acquire))
{
self.inner
.stats
.cohort_promotions
.fetch_add(1, Ordering::Relaxed);
}
}
let mut empty_kept = 0;
for entry in class.recent[..limit].iter().flatten() {
if entry.span.live() != 0 || entry.span.is_cohort_sealed() {
continue;
}
if empty_kept < self.inner.config.empty_spans_per_class {
empty_kept += 1;
continue;
}
if class.magazine.pointer == entry.pointer() {
class
.magazine
.flush(self.inner.config.recent_free_word_hints);
}
if entry.span.try_recycle_empty_cohort(owner) {
self.inner
.stats
.cohort_recycles
.fetch_add(1, Ordering::Relaxed);
}
}
}
#[inline]
fn cohort_limit(&self, class_index: usize) -> usize {
if SIZE_CLASSES[class_index] <= 4096 {
self.inner.config.young_ring_spans
} else {
0
}
}
#[inline]
fn try_deallocate_to_local_magazine(
&self,
last: LastLocalCache,
span: &SpanDesc,
address: usize,
layout: Layout,
class_index: usize,
) -> bool {
if self.inner.config.local_magazine_capacity == 0 || span.is_cohort_sealed() {
return false;
}
let epoch = self.inner.trim_epoch.load(Ordering::Acquire);
let local = unsafe { &mut *last.pointer };
if local.trim_epoch != epoch {
return false;
}
#[cfg(debug_assertions)]
if local.active.replace(true) {
return false;
}
let _access = LocalCacheAccess {
#[cfg(debug_assertions)]
active: &local.active,
};
let territory_cached = territory_cache_index(class_index)
.and_then(|cache_index| {
local.low_capacity_territories[cache_index].get_by_base(span.base)
})
.is_some_and(|cached| {
std::ptr::eq(cached.pointer(), span)
&& cached.generation == span.generation.load(Ordering::Acquire)
});
let pointer = span as *const SpanDesc;
debug_assert_eq!(span.class_index(), Some(class_index));
let class = &mut local.classes[class_index];
let generation = if class.magazine.leased && class.magazine.pointer == pointer {
class.magazine.generation
} else {
if class.magazine.leased {
class
.magazine
.flush(self.inner.config.recent_free_word_hints);
}
span.generation.load(Ordering::Acquire)
};
if class.magazine.leased && class.magazine.generation != generation {
class
.magazine
.flush(self.inner.config.recent_free_word_hints);
}
if !class.magazine.leased {
if span.live() as usize > self.inner.config.local_magazine_capacity {
return false;
}
let cached = territory_cached
|| class.recent[..self.inner.config.recent_spans_per_class]
.iter()
.any(|entry| {
entry.as_ref().is_some_and(|entry| {
entry.pointer() == pointer && entry.generation == generation
})
});
if !cached || !span.try_acquire_local_cache_lease(last.owner, generation, class_index) {
return false;
}
class.magazine.pointer = pointer;
class.magazine.generation = generation;
class.magazine.leased = true;
span.synchronize_remote_accounting();
}
unsafe {
self.deallocate_to_leased_magazine(
class,
span,
address,
layout,
class_index,
last.owner,
generation,
)
};
true
}
#[inline]
#[allow(clippy::too_many_arguments)]
unsafe fn deallocate_to_leased_magazine(
&self,
class: &mut CachedClass,
span: &SpanDesc,
address: usize,
layout: Layout,
class_index: usize,
owner: u64,
generation: u64,
) {
if class.magazine.target == 0 {
class.magazine.target = 1;
}
let target = class
.magazine
.target
.min(self.inner.config.local_magazine_capacity)
.min(span.capacity() as usize);
let cached_address = unsafe {
span.deallocate_small_to_local_cache(address, owner, generation, class_index)
};
class.magazine.record_deallocation(layout);
if class.magazine.len == target {
if class.magazine.target == self.inner.config.local_magazine_capacity {
unsafe { class.magazine.push_overflow(cached_address) };
return;
}
let (_, _, spill) = class
.magazine
.pop()
.expect("a full magazine has a block to spill");
span.publish_local_cached_address(spill, self.inner.config.recent_free_word_hints);
}
class.magazine.push_leased(cached_address, target);
}
#[inline]
fn with_local_cache<R>(&self, operation: impl FnOnce(&mut LocalCache) -> R) -> R {
let epoch = self.inner.trim_epoch.load(Ordering::Acquire);
LAST_LOCAL_CACHE.with(|last_cache| {
let last = last_cache.get();
let pointer = if last.allocator_id == self.inner.id && !last.pointer.is_null() {
last.pointer
} else {
let (pointer, owner) = LOCAL_STATE.with(|state| {
let mut caches = state.caches.borrow_mut();
let local = caches.entry(self.inner.id).or_insert_with(|| {
let owner = NEXT_OWNER_TOKEN.fetch_add(1, Ordering::Relaxed).max(1);
let seed = self
.inner
.config
.random_seed
.unwrap_or(self.inner.id.rotate_left(17) ^ owner.rotate_right(7));
Box::new(LocalCache {
#[cfg(debug_assertions)]
active: Cell::new(false),
inner: Arc::downgrade(&self.inner),
epoch_handle: self.inner.collector.register(),
owner,
trim_epoch: epoch,
rng: seed.max(1),
classes: std::array::from_fn(|_| CachedClass::default()),
low_capacity_territories: std::array::from_fn(|_| {
TerritoryCache::default()
}),
runs: std::array::from_fn(|_| None),
dedicated_runs: std::array::from_fn(|_| None),
run_windows: std::array::from_fn(|_| RunLocalWindow::default()),
run_len: 0,
dedicated_run_len: 0,
run_cursor: 0,
dedicated_run_cursor: 0,
run_window_cursor: 0,
})
});
(&mut **local as *mut LocalCache, local.owner)
});
last_cache.set(LastLocalCache {
allocator_id: self.inner.id,
owner,
pointer,
});
pointer
};
#[cfg(debug_assertions)]
let active = unsafe { std::ptr::addr_of!((*pointer).active) };
#[cfg(debug_assertions)]
assert!(
!unsafe { (*active).replace(true) },
"reentrant local cache access"
);
let _access = LocalCacheAccess {
#[cfg(debug_assertions)]
active,
};
let local = unsafe { &mut *pointer };
if local.trim_epoch != epoch {
self.refresh_local_cache(local, epoch);
}
operation(local)
})
}
fn refresh_local_cache(&self, local: &mut LocalCache, epoch: u64) {
for (class_index, class) in local.classes.iter_mut().enumerate() {
unsafe { class.remote.flush(class_index) };
class
.magazine
.flush(self.inner.config.recent_free_word_hints);
class
.black_ring
.flush(self.inner.config.recent_free_word_hints);
}
for cached in local
.classes
.iter()
.flat_map(|class| class.recent.iter().flatten())
{
let span = &*cached.span;
if span.live() == 0 {
let _ = span.owner.compare_exchange(
local.owner,
0,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
local.classes.fill_with(CachedClass::default);
local
.low_capacity_territories
.fill_with(TerritoryCache::default);
for cached in local
.runs
.iter()
.chain(local.dedicated_runs.iter())
.flatten()
{
let span = &*cached.span;
let _ =
span.owner
.compare_exchange(local.owner, 0, Ordering::AcqRel, Ordering::Acquire);
}
local.runs.fill(None);
local.dedicated_runs.fill(None);
for window in &mut local.run_windows {
let released = window.release();
self.inner
.stats
.run_local_window_releases
.fetch_add(released as u64, Ordering::Relaxed);
}
local.run_len = 0;
local.dedicated_run_len = 0;
local.run_cursor = 0;
local.dedicated_run_cursor = 0;
local.run_window_cursor = 0;
local.trim_epoch = epoch;
}
fn refresh_current_local_cache(&self, epoch: u64) {
LOCAL_STATE.with(|state| {
let mut caches = state.caches.borrow_mut();
let Some(local) = caches.get_mut(&self.inner.id) else {
return;
};
#[cfg(debug_assertions)]
assert!(!local.active.replace(true), "reentrant local cache refresh");
let _access = LocalCacheAccess {
#[cfg(debug_assertions)]
active: &local.active,
};
self.refresh_local_cache(local, epoch);
});
}
fn with_topology_snapshot<R>(&self, operation: impl FnOnce(&TopologyReadSnapshot) -> R) -> R {
LOCAL_STATE.with(|state| {
let caches = state.caches.borrow();
let local = caches
.get(&self.inner.id)
.expect("allocation initialized its TLS cache before snapshot search");
let guard = local.epoch_handle.pin();
let shared = self.inner.topology_snapshot.load(Ordering::Acquire, &guard);
operation(unsafe { shared.deref() })
})
}
}
struct ExtentTransaction<'a>(&'a Inner);
impl Drop for ExtentTransaction<'_> {
fn drop(&mut self) {
let previous = self.0.extent_control.fetch_sub(1, Ordering::Release);
debug_assert_ne!(previous & !MAINTENANCE_BIT, 0);
}
}
struct MaintenanceGate<'a>(&'a Inner);
impl Drop for MaintenanceGate<'_> {
fn drop(&mut self) {
let previous = self
.0
.extent_control
.fetch_and(!MAINTENANCE_BIT, Ordering::Release);
debug_assert_eq!(previous, MAINTENANCE_BIT);
}
}
impl Drop for Inner {
fn drop(&mut self) {
let topology = self
.topology
.get_mut()
.expect("topology lock poisoned during drop");
debug_assert_eq!(
topology
.tree
.values()
.iter()
.map(|span| span.requested_live())
.sum::<usize>(),
0,
"dropping bomalloc with live allocations"
);
for span in topology.tree.values() {
if matches!(
span.kind(),
SpanKind::Dedicated | SpanKind::DedicatedReserved
) {
let _ = unsafe { self.backing.release(span.base, span.size) };
}
}
for chunk in &topology.chunks {
let _ = unsafe { self.backing.release(chunk.base, chunk.size) };
}
let guard = unsafe { crossbeam_epoch::unprotected() };
let current = self
.topology_snapshot
.swap(Shared::null(), Ordering::AcqRel, guard);
if !current.is_null() {
unsafe { drop(current.into_owned()) };
}
}
}
fn xorshift(mut value: u64) -> u64 {
value ^= value << 13;
value ^= value >> 7;
value ^= value << 17;
value
}
#[inline]
fn next_cohort_epoch(current: u64) -> u64 {
let next = current.wrapping_add(1) & !(1_u64 << 63);
next.max(1)
}
#[inline]
fn jump_seed(owner: u64, rotate: usize, class_index: usize) -> u64 {
let mixed = owner.rotate_left(19)
^ (rotate as u64).rotate_right(11)
^ (class_index as u64 + 1).wrapping_mul(0x9e37_79b9_7f4a_7c15);
xorshift(mixed).max(1)
}
#[inline]
fn coprime_step(seed: usize, length: usize) -> usize {
if length <= 1 {
return 1;
}
let mut step = seed % length;
if step == 0 {
step = 1;
}
while gcd(step, length) != 1 {
step += 1;
if step == length {
step = 1;
}
}
step
}
#[inline]
fn gcd(mut left: usize, mut right: usize) -> usize {
while right != 0 {
(left, right) = (right, left % right);
}
left
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::mpsc;
use std::thread;
use std::time::Duration;
#[test]
fn size_classes_honor_size_and_alignment() {
let config = Config::default();
for align in [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096] {
for size in 1..=config.small_max {
assert_eq!(
config.is_small_layout(size, align),
config.class_for(size, align).is_some()
);
if let Some(index) = config.class_for(size, align) {
assert!(SIZE_CLASSES[index] >= size);
assert_eq!(SIZE_CLASSES[index] % align, 0);
}
}
}
assert!(!config.is_small_layout(config.small_max + 1, 8));
assert!(!config.is_small_layout(8, 8192));
}
#[test]
fn headerless_large_small_spans_use_the_full_64_kib_payload() {
for (size, capacity) in [(32 * 1024, 2_usize)] {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(size, 4096).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let mut pointers = Vec::with_capacity(capacity);
for index in 0..capacity {
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
let base = pointer.as_ptr() as usize & !(SMALL_SPAN_SIZE - 1);
assert_eq!(pointer.as_ptr() as usize, base + index * size);
pointers.push(pointer);
}
assert_eq!(allocator.stats().committed_bytes, SMALL_SPAN_SIZE);
let base = pointers[0].as_ptr() as usize;
let last = LAST_LOCAL_CACHE.with(|last| last.get());
let descriptor = allocator
.try_resolve_headerless_cached_span(Some(last), class_index, base)
.expect("the owner resolves a headerless span directly from TLS");
assert_eq!(unsafe { (*descriptor).capacity() }, capacity as u32);
for pointer in pointers.into_iter().rev() {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.trim(TrimMode::Aggressive);
allocator.validate().unwrap();
}
}
#[test]
fn foreign_headerless_free_resolves_through_the_lock_free_tree() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(32 * 1024, 4096).unwrap();
let allocation = allocator.allocate(layout).unwrap();
let address = allocation.as_ptr() as *mut u8 as usize;
let consumer = allocator.clone();
thread::spawn(move || {
unsafe {
consumer.deallocate(NonNull::new(address as *mut u8).unwrap(), layout);
}
})
.join()
.unwrap();
assert_eq!(allocator.stats().requested_live_bytes, 0);
let first = allocator.allocate(layout).unwrap();
let second = allocator.allocate(layout).unwrap();
assert!(
[
first.as_ptr() as *mut u8 as usize,
second.as_ptr() as *mut u8 as usize,
]
.contains(&address)
);
for recycled in [first, second] {
unsafe {
allocator.deallocate(NonNull::new(recycled.as_ptr() as *mut u8).unwrap(), layout);
}
}
allocator.validate().unwrap();
}
#[test]
fn xorshift_changes_nonzero_seed() {
assert_ne!(xorshift(1), 1);
assert_ne!(xorshift(1), 0);
}
#[test]
fn jump_stride_visits_every_candidate_once() {
for length in 1..=128 {
for seed in 0..=length * 2 {
let step = coprime_step(seed, length);
let mut visited = vec![false; length];
for offset in 0..length {
let index = offset * step % length;
assert!(
!visited[index],
"duplicate index for len={length} step={step}"
);
visited[index] = true;
}
assert!(visited.into_iter().all(|seen| seen));
}
}
}
#[test]
fn locality_window_prefers_same_chunk_then_nearest_address() {
let items = [
(100_usize, 10_usize),
(160, 20),
(180, 20),
(200, 20),
(220, 20),
(240, 30),
(300, 30),
];
let hint = LocalityHint {
address: 205,
chunk_base: 20,
};
let mut visited = Vec::new();
let result = visit_locality_window(
&items,
hint,
items.len(),
|item| item.0,
|item| item.1,
|item| {
visited.push(item.0);
(item.0 == 180).then_some(item.0)
},
);
assert_eq!(result, Some(180));
assert_eq!(visited, [200, 220, 180]);
visited.clear();
let result = visit_locality_window(
&items,
hint,
items.len(),
|item| item.0,
|item| item.1,
|item| {
visited.push(item.0);
None::<()>
},
);
assert_eq!(result, None);
assert_eq!(visited, [200, 220, 180, 160, 240, 300, 100]);
}
#[test]
fn boxed_local_cache_fast_pointer_survives_hash_map_growth() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let initial = allocator.with_local_cache(|local| local as *mut LocalCache);
for _ in 0..256 {
let other = BoAllocator::new(Config::default()).unwrap();
other.with_local_cache(|_| {});
}
let after_growth = allocator.with_local_cache(|local| local as *mut LocalCache);
assert_eq!(after_growth, initial);
let layout = Layout::from_size_align(96, 32).unwrap();
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
allocator.validate().unwrap();
}
#[test]
fn overflow_cache_hit_is_promoted_in_place() {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 2,
black_span_ring_capacity: 0,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(4096, 4096).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let mut pointers = Vec::new();
for _ in 0..45 {
let allocation = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let freed = pointers[15];
let freed_span = freed.as_ptr() as usize & !(SMALL_SPAN_SIZE - 1);
let before = allocator.with_local_cache(|local| {
(
local.classes[class_index].recent[0]
.as_ref()
.unwrap()
.span
.base,
local.classes[class_index].recent[1]
.as_ref()
.unwrap()
.span
.base,
)
});
assert_ne!(before.0, freed_span);
assert_eq!(before.1, freed_span);
unsafe { allocator.deallocate(freed, layout) };
let replacement = allocator.allocate(layout).unwrap();
let replacement = NonNull::new(replacement.as_ptr() as *mut u8).unwrap();
assert_eq!(replacement, freed);
let promoted = allocator.with_local_cache(|local| {
local.classes[class_index].recent[0]
.as_ref()
.unwrap()
.span
.base
});
assert_eq!(promoted, freed_span);
pointers[15] = replacement;
for pointer in pointers {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.validate().unwrap();
}
#[test]
fn snapshot_small_search_does_not_wait_for_topology_write_lock() {
let allocator = BoAllocator::new(Config {
red_cold_slow_paths: 0,
recent_spans_per_class: 1,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(64, 16).unwrap();
let pointer = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(pointer.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
let topology_guard = allocator.inner.topology.write().unwrap();
let worker_allocator = allocator.clone();
let (sender, receiver) = mpsc::channel();
let worker = thread::spawn(move || {
let allocation = worker_allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { worker_allocator.deallocate(pointer, layout) };
sender.send(()).unwrap();
});
receiver
.recv_timeout(Duration::from_secs(1))
.expect("snapshot search unexpectedly waited for the topology lock");
drop(topology_guard);
worker.join().unwrap();
}
#[test]
fn exact_small_tree_fallback_recovers_from_stale_snapshot() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(128, 64).unwrap();
let first = allocator.allocate(layout).unwrap();
let address = first.as_ptr() as *mut u8 as usize;
unsafe { allocator.deallocate(NonNull::new(address as *mut u8).unwrap(), layout) };
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
allocator.with_local_cache(|local| local.classes[class_index].recent.fill(None));
let spans_before = allocator.inner.address_tree.values().len();
allocator.publish_snapshot(TopologyReadSnapshot::empty());
let second = allocator.allocate(layout).unwrap();
assert_eq!(second.as_ptr() as *mut u8 as usize, address);
assert_eq!(allocator.inner.address_tree.values().len(), spans_before);
unsafe { allocator.deallocate(NonNull::new(second.as_ptr() as *mut u8).unwrap(), layout) };
allocator.validate().unwrap();
}
#[test]
fn stats_reads_the_concurrent_address_tree_without_topology_lock() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(128, 64).unwrap();
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
let topology_guard = allocator.inner.topology.write().unwrap();
let reader_allocator = allocator.clone();
let (sender, receiver) = mpsc::channel();
let reader = thread::spawn(move || {
sender.send(reader_allocator.stats()).unwrap();
});
let snapshot = receiver
.recv_timeout(Duration::from_secs(1))
.expect("stats unexpectedly waited for the topology lock");
assert_eq!(snapshot.requested_live_bytes, layout.size());
drop(topology_guard);
reader.join().unwrap();
unsafe { allocator.deallocate(pointer, layout) };
}
#[test]
fn reusable_run_snapshot_does_not_wait_for_topology_write_lock() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
let worker_allocator = allocator.clone();
let (ready_sender, ready_receiver) = mpsc::channel();
let (continue_sender, continue_receiver) = mpsc::channel();
let (done_sender, done_receiver) = mpsc::channel();
let worker = thread::spawn(move || {
let allocation = worker_allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { worker_allocator.deallocate(pointer, layout) };
ready_sender.send(()).unwrap();
continue_receiver.recv().unwrap();
let allocation = worker_allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { worker_allocator.deallocate(pointer, layout) };
done_sender.send(()).unwrap();
});
ready_receiver.recv().unwrap();
let topology_guard = allocator.inner.topology.write().unwrap();
continue_sender.send(()).unwrap();
done_receiver
.recv_timeout(Duration::from_secs(1))
.expect("owner-local run reuse unexpectedly waited for the topology lock");
drop(topology_guard);
worker.join().unwrap();
}
#[test]
fn concurrent_run_extent_creation_does_not_need_the_topology_lock() {
const WORKERS: usize = 8;
let allocator = BoAllocator::new(Config::default()).unwrap();
let small_layout = Layout::from_size_align(128, 64).unwrap();
let seed = allocator.allocate(small_layout).unwrap();
unsafe {
allocator.deallocate(
NonNull::new(seed.as_ptr() as *mut u8).unwrap(),
small_layout,
);
}
let topology_guard = allocator.inner.topology.write().unwrap();
let barrier = Arc::new(std::sync::Barrier::new(WORKERS));
let (sender, receiver) = mpsc::channel();
let mut workers = Vec::new();
for _ in 0..WORKERS {
let allocator = allocator.clone();
let barrier = Arc::clone(&barrier);
let sender = sender.clone();
workers.push(thread::spawn(move || {
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
barrier.wait();
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
sender.send(()).unwrap();
}));
}
drop(sender);
for _ in 0..WORKERS {
if receiver.recv_timeout(Duration::from_secs(1)).is_err() {
let spans = allocator.inner.address_tree.values();
let free_total = spans
.iter()
.filter(|span| span.kind() == SpanKind::Free)
.count();
let free_available = spans.iter().filter(|span| span.is_available_free()).count();
panic!(
"lock-free run extent creation stalled: in_flight={}, free_total={free_total}, free_available={free_available}, spans={}",
allocator
.inner
.free_claims_in_flight
.load(Ordering::Acquire),
spans.len()
);
}
}
drop(topology_guard);
for worker in workers {
worker.join().unwrap();
}
allocator.validate().unwrap();
}
#[test]
fn concurrent_small_territory_creation_does_not_need_the_topology_lock() {
const WORKERS: usize = 8;
let allocator = BoAllocator::new(Config::default()).unwrap();
assert!(
allocator
.ensure_chunk_for_extent(SMALL_SPAN_SIZE, SMALL_SPAN_SIZE)
.unwrap()
);
let topology_guard = allocator.inner.topology.write().unwrap();
let barrier = Arc::new(std::sync::Barrier::new(WORKERS));
let (sender, receiver) = mpsc::channel();
let mut workers = Vec::new();
for _ in 0..WORKERS {
let allocator = allocator.clone();
let barrier = Arc::clone(&barrier);
let sender = sender.clone();
workers.push(thread::spawn(move || {
let layout = Layout::from_size_align(128, 64).unwrap();
barrier.wait();
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
sender.send(()).unwrap();
}));
}
drop(sender);
for _ in 0..WORKERS {
receiver
.recv_timeout(Duration::from_secs(1))
.expect("lock-free small territory creation stalled");
}
drop(topology_guard);
for worker in workers {
worker.join().unwrap();
}
allocator.validate().unwrap();
}
#[test]
fn maintenance_gate_serializes_trim_with_lock_free_extent_growth() {
const WORKERS: usize = 4;
let allocator = BoAllocator::new(Config::default()).unwrap();
let barrier = Arc::new(std::sync::Barrier::new(WORKERS + 1));
let mut workers = Vec::new();
for worker_index in 0..WORKERS {
let allocator = allocator.clone();
let barrier = Arc::clone(&barrier);
workers.push(thread::spawn(move || {
barrier.wait();
for iteration in 0..400 {
let layout = if (worker_index + iteration) % 2 == 0 {
Layout::from_size_align(128, 64).unwrap()
} else {
Layout::from_size_align(64 * 1024, 4096).unwrap()
};
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
}
}));
}
let trimmer = {
let allocator = allocator.clone();
let barrier = Arc::clone(&barrier);
thread::spawn(move || {
barrier.wait();
for _ in 0..100 {
allocator.trim(TrimMode::Aggressive);
}
})
};
for worker in workers {
worker.join().unwrap();
}
trimmer.join().unwrap();
allocator.validate().unwrap();
}
#[test]
fn run_growth_uses_one_stable_territory_and_adaptive_local_window() {
let allocator = BoAllocator::new(Config {
run_local_window_capacity: crate::config::MAX_RUN_LOCAL_WINDOW_CAPACITY,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
let page = allocator.inner.backing.page_size();
let needed = layout.size() + size_of::<RunHeader>() + layout.align() - 1;
let extent_size = align_up(needed, page).unwrap();
assert!(
allocator
.ensure_chunk_for_extent(extent_size, page)
.unwrap()
);
let allocation = allocator.allocate(layout).unwrap();
let runs: Vec<_> = allocator
.inner
.address_tree
.values()
.into_iter()
.filter(|span| matches!(span.kind(), SpanKind::Run | SpanKind::ReservedRun))
.collect();
assert_eq!(runs.len(), 1);
let territory = &runs[0];
assert!(territory.is_run_territory());
assert_eq!(territory.size, RECENT_RUNS * extent_size);
assert_eq!(territory.capacity(), RECENT_RUNS as u32);
assert_eq!(territory.run_extent_size(), Some(extent_size));
assert_eq!(territory.run_high_water(), 1);
assert_eq!(territory.live(), 1);
assert_eq!(allocator.stats().committed_bytes, extent_size);
let mut pointers = vec![NonNull::new(allocation.as_ptr() as *mut u8).unwrap()];
for _ in 1..=INITIAL_RUN_TERRITORY_EXTENTS {
let allocation = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let stats = allocator.stats();
let expected_high_water = 15;
assert_eq!(stats.committed_bytes, expected_high_water * extent_size);
assert_eq!(stats.reserved_run_activations, 14);
assert_eq!(stats.run_territory_extensions, 1);
assert_eq!(stats.run_territory_extension_extents, 7);
assert_eq!(stats.run_local_window_refills, 3);
assert_eq!(stats.run_local_window_hits, 5);
let extended: Vec<_> = allocator
.inner
.address_tree
.values()
.into_iter()
.filter(|span| matches!(span.kind(), SpanKind::Run | SpanKind::ReservedRun))
.collect();
assert_eq!(extended.len(), 1);
assert_eq!(extended[0].run_high_water(), expected_high_water as u32);
assert_eq!(extended[0].live(), 9);
assert!(
pointers
.windows(2)
.all(|pair| pair[1].as_ptr() as usize - pair[0].as_ptr() as usize == extent_size)
);
let recycled = pointers.swap_remove(4);
unsafe { allocator.deallocate(recycled, layout) };
let committed = allocator.stats().committed_bytes;
let mut window_allocations = Vec::new();
for _ in 0..6 {
let allocation = allocator.allocate(layout).unwrap();
window_allocations.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let reused = allocator.allocate(layout).unwrap();
let reused = NonNull::new(reused.as_ptr() as *mut u8).unwrap();
assert_eq!(
reused, recycled,
"the drained window returns to recycled holes"
);
assert_eq!(allocator.stats().committed_bytes, committed);
pointers.push(reused);
pointers.extend(window_allocations);
for pointer in pointers {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.validate().unwrap();
let trimmed = allocator.trim(TrimMode::Aggressive);
assert_eq!(trimmed.bytes_decommitted, expected_high_water * extent_size);
assert_eq!(allocator.stats().reserved_bytes, 0);
allocator.validate().unwrap();
}
#[test]
fn disabled_run_extension_preserves_the_eight_run_baseline() {
let allocator = BoAllocator::new(Config {
adaptive_run_territory_extension_extents: 0,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
let mut pointers = Vec::with_capacity(INITIAL_RUN_TERRITORY_EXTENTS + 1);
for _ in 0..=INITIAL_RUN_TERRITORY_EXTENTS {
let allocation = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let stats = allocator.stats();
assert_eq!(stats.run_territory_extensions, 0);
assert_eq!(stats.run_territory_extension_extents, 0);
assert_eq!(stats.tree_batch_replacements, 2);
for pointer in pointers.into_iter().rev() {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.trim(TrimMode::Aggressive);
allocator.validate().unwrap();
}
#[test]
fn aggressive_trim_republishes_unused_run_window_slots() {
let allocator = BoAllocator::new(Config {
run_local_window_capacity: crate::config::MAX_RUN_LOCAL_WINDOW_CAPACITY,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
let page = allocator.inner.backing.page_size();
let needed = layout.size() + size_of::<RunHeader>() + layout.align() - 1;
let extent_size = align_up(needed, page).unwrap();
let first = allocator.allocate(layout).unwrap();
let second = allocator.allocate(layout).unwrap();
assert_eq!(allocator.stats().committed_bytes, 3 * extent_size);
assert_eq!(allocator.stats().run_local_window_refills, 1);
assert_eq!(allocator.stats().run_local_window_releases, 0);
allocator.trim(TrimMode::Aggressive);
assert_eq!(allocator.stats().run_local_window_releases, 1);
assert_eq!(allocator.stats().committed_bytes, 3 * extent_size);
let third = allocator.allocate(layout).unwrap();
assert_eq!(
third.as_ptr() as *mut u8 as usize - first.as_ptr() as *mut u8 as usize,
2 * extent_size
);
assert_eq!(allocator.stats().committed_bytes, 3 * extent_size);
for allocation in [first, second, third] {
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.trim(TrimMode::Aggressive);
allocator.validate().unwrap();
}
#[test]
fn exhausted_small_territory_extends_its_adjacent_free_suffix() {
let allocator = BoAllocator::new(Config {
locality_reserve_spans: 1,
adaptive_territory_extension_spans: 3,
recent_spans_per_class: 1,
local_magazine_capacity: 0,
black_span_ring_capacity: 0,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(1024, 1024).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let capacity = small_span_capacity(class_index);
let mut pointers = Vec::with_capacity(capacity + 1);
for _ in 0..=capacity {
let allocation = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let stats = allocator.stats();
assert_eq!(stats.territory_extensions, 1);
assert_eq!(stats.territory_extension_spans, 3);
assert_eq!(stats.global_searches, 0);
let spans = allocator.inner.address_tree.values();
let mut territory: Vec<_> = spans
.into_iter()
.filter(|span| span.class_index() == Some(class_index))
.collect();
territory.sort_by_key(|span| span.base);
assert_eq!(territory.len(), 4);
assert!(
territory
.windows(2)
.all(|pair| pair[0].base + SMALL_SPAN_SIZE == pair[1].base)
);
assert_eq!(
territory
.iter()
.filter(|span| span.kind() == SpanKind::ReservedSmall)
.count(),
2
);
for pointer in pointers.into_iter().rev() {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.validate().unwrap();
}
#[test]
fn reserved_run_activation_does_not_take_topology_lock() {
let allocator = BoAllocator::new(Config {
run_local_window_capacity: 0,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
let page = allocator.inner.backing.page_size();
let needed = layout.size() + size_of::<RunHeader>() + layout.align() - 1;
let extent_size = align_up(needed, page).unwrap();
assert!(
allocator
.ensure_chunk_for_extent(extent_size, page)
.unwrap()
);
let first = allocator.allocate(layout).unwrap();
let topology_guard = allocator.inner.topology.write().unwrap();
let second = allocator
.allocate(layout)
.expect("ReservedRun activation must not acquire the topology lock");
assert_eq!(allocator.stats().committed_bytes, 2 * extent_size);
assert_eq!(allocator.stats().reserved_run_activations, 1);
drop(topology_guard);
for allocation in [first, second] {
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.trim(TrimMode::Aggressive);
assert_eq!(allocator.stats().committed_bytes, 0);
allocator.validate().unwrap();
}
#[test]
fn pinned_reader_keeps_replaced_snapshot_alive() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(128, 64).unwrap();
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
let reader_allocator = allocator.clone();
let (entered_sender, entered_receiver) = mpsc::channel();
let (release_sender, release_receiver) = mpsc::channel();
let reader = thread::spawn(move || {
reader_allocator.with_local_cache(|_| ());
reader_allocator.with_topology_snapshot(|snapshot| {
entered_sender.send(()).unwrap();
release_receiver.recv().unwrap();
let spans = snapshot.class_spans(7);
assert_eq!(spans.len(), Config::default().small_territory_spans(7));
assert_ne!(spans[0].base, 0);
});
});
entered_receiver.recv().unwrap();
allocator.trim(TrimMode::Aggressive);
release_sender.send(()).unwrap();
reader.join().unwrap();
}
#[test]
fn locality_window_recovers_capacity_outside_single_span_cache() {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
black_span_ring_capacity: 0,
locality_window_spans: 8,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(4096, 4096).unwrap();
let mut live = Vec::new();
for _ in 0..32 {
let allocation = allocator.allocate(layout).unwrap();
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let first = live.remove(0);
unsafe { allocator.deallocate(first, layout) };
for _ in 0..13 {
let allocation = allocator.allocate(layout).unwrap();
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let recycled = allocator.allocate(layout).unwrap();
let recycled = NonNull::new(recycled.as_ptr() as *mut u8).unwrap();
assert_eq!(recycled, first);
live.push(recycled);
assert!(allocator.stats().locality_hits >= 1);
for pointer in live {
unsafe { allocator.deallocate(pointer, layout) };
}
}
#[test]
fn locality_window_claims_an_evicted_white_span_before_global_search() {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
local_magazine_capacity: 0,
low_capacity_page_queue_spans: 0,
locality_window_spans: 8,
locality_reserve_spans: 4,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(32 * 1024, 4096).unwrap();
let class_index = allocator.inner.config.class_for(32 * 1024, 4096).unwrap();
let mut live = Vec::new();
for _ in 0..4 {
let allocation = allocator.allocate(layout).unwrap();
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let first_base = live[0].as_ptr() as usize & !(SMALL_SPAN_SIZE - 1);
let second_base = live[2].as_ptr() as usize & !(SMALL_SPAN_SIZE - 1);
assert_ne!(first_base, second_base);
let spans = allocator.inner.address_tree.values();
let first_span = spans
.iter()
.find(|span| span.base == first_base)
.expect("first active span remains in the tree")
.clone();
let second_span = spans
.iter()
.find(|span| span.base == second_base)
.expect("second active span remains in the tree")
.clone();
for pointer in live.drain(2..) {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.cache_span(class_index, &first_span);
let owner = allocator.with_local_cache(|local| local.owner);
assert_eq!(first_span.owner.load(Ordering::Acquire), owner);
assert_eq!(second_span.owner.load(Ordering::Acquire), 0);
let before = allocator.stats();
let allocation = allocator.allocate(layout).unwrap();
let reused = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
let after = allocator.stats();
assert_eq!(
reused.as_ptr() as usize & !(SMALL_SPAN_SIZE - 1),
second_base
);
assert_eq!(after.global_searches, before.global_searches);
assert!(after.locality_hits > before.locality_hits);
live.push(reused);
for pointer in live {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.validate().unwrap();
}
#[test]
fn territory_return_hint_avoids_global_scan_between_disjoint_groups() {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
local_magazine_capacity: 0,
low_capacity_page_queue_spans: 0,
locality_window_spans: 4,
locality_reserve_spans: 4,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(32 * 1024, 4096).unwrap();
let mut first_wave = Vec::new();
for _ in 0..16 {
let allocation = allocator.allocate(layout).unwrap();
first_wave.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let first_addresses: std::collections::HashSet<_> = first_wave
.iter()
.map(|pointer| pointer.as_ptr() as usize)
.collect();
for pointer in first_wave {
unsafe { allocator.deallocate(pointer, layout) };
}
let before = allocator.stats();
let mut second_wave = Vec::new();
for _ in 0..16 {
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
assert!(first_addresses.contains(&(pointer.as_ptr() as usize)));
second_wave.push(pointer);
}
let after = allocator.stats();
assert_eq!(after.global_searches, before.global_searches);
assert!(after.locality_hits > before.locality_hits);
for pointer in second_wave {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.validate().unwrap();
}
#[test]
fn two_object_classes_cache_one_revalidated_territory_without_overlap() {
for class_index in [22, 23] {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
..Config::default()
})
.unwrap();
let size = SIZE_CLASSES[class_index];
let layout = Layout::from_size_align(size, 4096).unwrap();
let mut pointers = Vec::new();
let mut addresses = std::collections::HashSet::new();
for _ in 0..64 {
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
assert!(addresses.insert(pointer.as_ptr() as usize));
pointers.push(pointer);
}
allocator.with_local_cache(|local| {
let cache =
&local.low_capacity_territories[territory_cache_index(class_index).unwrap()];
assert_eq!(cache.len, 32);
assert!(cache.spans[..cache.len].iter().all(Option::is_some));
assert!(cache.spans[..cache.len].windows(2).all(|pair| {
pair[1].as_ref().unwrap().span.base - pair[0].as_ref().unwrap().span.base
== SMALL_SPAN_SIZE
}));
});
let (owner, middle_base, chunk_base) = allocator.with_local_cache(|local| {
let cache_index = territory_cache_index(class_index).unwrap();
let cache = &mut local.low_capacity_territories[cache_index];
let middle = cache.spans[cache.len / 2].as_ref().unwrap();
let result = (local.owner, middle.span.base, middle.span.chunk_base);
cache.spans.fill(None);
cache.len = 0;
cache.cursor = 0;
result
});
allocator.ensure_low_capacity_territory_at(class_index, owner, middle_base, chunk_base);
allocator.with_local_cache(|local| {
let cache =
&local.low_capacity_territories[territory_cache_index(class_index).unwrap()];
assert_eq!(cache.len, 32);
assert!(cache.spans[..cache.len].windows(2).all(|pair| {
pair[1].as_ref().unwrap().span.base - pair[0].as_ref().unwrap().span.base
== SMALL_SPAN_SIZE
}));
});
if class_index == 23 {
let first = pointers.first().unwrap().as_ptr() as usize;
let base = first & !(SMALL_SPAN_SIZE - 1);
let last = LAST_LOCAL_CACHE.with(|last| Some(last.get()));
assert!(
allocator
.try_resolve_headerless_cached_span(last, class_index, base)
.is_some()
);
}
let first_span_base = pointers[0].as_ptr() as usize & !(SMALL_SPAN_SIZE - 1);
for pointer in pointers.into_iter().rev() {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert_eq!(unsafe { (*magazine.pointer).base }, first_span_base);
});
allocator.trim(TrimMode::Aggressive);
allocator.with_local_cache(|local| {
let cache =
&local.low_capacity_territories[territory_cache_index(class_index).unwrap()];
assert_eq!(cache.len, 0);
});
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
allocator.validate().unwrap();
}
}
#[test]
fn small_span_growth_uses_a_contiguous_soft_territory() {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
locality_reserve_spans: 8,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(4096, 4096).unwrap();
let mut live = Vec::new();
for _ in 0..32 {
let allocation = allocator.allocate(layout).unwrap();
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let topology = allocator.inner.topology.read().unwrap();
let small_bases: Vec<_> = topology
.tree
.values()
.into_iter()
.filter(|span| span.kind() == SpanKind::Small)
.map(|span| span.base)
.collect();
assert_eq!(small_bases.len(), 3);
assert!(
small_bases
.windows(2)
.all(|pair| pair[1] - pair[0] == SMALL_SPAN_SIZE)
);
assert!(topology.tree.values().iter().any(|span| {
span.kind() == SpanKind::ReservedSmall && span.owner.load(Ordering::Acquire) != 0
}));
drop(topology);
for pointer in live {
unsafe { allocator.deallocate(pointer, layout) };
}
}
#[test]
fn concurrent_owners_receive_contiguous_soft_territories() {
const THREADS: usize = 8;
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
locality_reserve_spans: 8,
..Config::default()
})
.unwrap();
let ready = Arc::new(std::sync::Barrier::new(THREADS + 1));
let release = Arc::new(std::sync::Barrier::new(THREADS + 1));
let mut workers = Vec::new();
for _ in 0..THREADS {
let allocator = allocator.clone();
let ready = Arc::clone(&ready);
let release = Arc::clone(&release);
workers.push(thread::spawn(move || {
let layout = Layout::from_size_align(4096, 4096).unwrap();
let mut live = Vec::new();
for _ in 0..32 {
let allocation = allocator.allocate(layout).unwrap();
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
ready.wait();
release.wait();
for pointer in live {
unsafe { allocator.deallocate(pointer, layout) };
}
}));
}
ready.wait();
let topology = allocator.inner.topology.read().unwrap();
let mut by_owner: HashMap<u64, Vec<usize>> = HashMap::new();
for span in topology.tree.values() {
if span.kind() == SpanKind::Small {
by_owner
.entry(span.owner.load(Ordering::Acquire))
.or_default()
.push(span.base);
}
}
assert_eq!(by_owner.len(), THREADS);
for bases in by_owner.values_mut() {
bases.sort_unstable();
assert_eq!(bases.len(), 3);
assert!(
bases
.windows(2)
.all(|pair| pair[1] - pair[0] == SMALL_SPAN_SIZE)
);
}
drop(topology);
release.wait();
for worker in workers {
worker.join().unwrap();
}
}
#[test]
fn thread_exit_releases_all_empty_spans_and_soft_territories() {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
locality_reserve_spans: 8,
..Config::default()
})
.unwrap();
let worker_allocator = allocator.clone();
thread::spawn(move || {
let layout = Layout::from_size_align(4096, 4096).unwrap();
let mut live = Vec::new();
for _ in 0..32 {
let allocation = worker_allocator.allocate(layout).unwrap();
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
for pointer in live {
unsafe { worker_allocator.deallocate(pointer, layout) };
}
})
.join()
.unwrap();
let topology = allocator.inner.topology.read().unwrap();
assert!(topology.tree.values().iter().all(|span| {
!matches!(
span.kind(),
SpanKind::Small | SpanKind::ReservedSmall | SpanKind::ReservedRun | SpanKind::Free
) || span.owner.load(Ordering::Acquire) == 0
}));
}
#[test]
fn thread_exit_releases_live_run_soft_ownership() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
let worker_allocator = allocator.clone();
let address = thread::spawn(move || {
worker_allocator.allocate(layout).unwrap().as_ptr() as *mut u8 as usize
})
.join()
.unwrap();
let run = allocator
.inner
.address_tree
.values()
.into_iter()
.find(|span| span.kind() == SpanKind::Run)
.unwrap();
assert_eq!(run.owner.load(Ordering::Acquire), 0);
unsafe {
allocator.deallocate(NonNull::new(address as *mut u8).unwrap(), layout);
}
let recycled = allocator.allocate(layout).unwrap();
assert_eq!(recycled.as_ptr() as *mut u8 as usize, address);
unsafe {
allocator.deallocate(NonNull::new(recycled.as_ptr() as *mut u8).unwrap(), layout);
}
}
#[test]
fn reserved_span_activation_does_not_take_topology_write_lock() {
let allocator = BoAllocator::new(Config {
recent_spans_per_class: 1,
locality_reserve_spans: 8,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(4096, 4096).unwrap();
let mut live = Vec::new();
for _ in 0..15 {
let allocation = allocator.allocate(layout).unwrap();
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
let publishes = allocator.stats().topology_snapshot_publishes;
let topology_guard = allocator.inner.topology.write().unwrap();
let allocation = allocator
.allocate(layout)
.expect("reserved activation must not reacquire the topology lock");
live.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
assert_eq!(
allocator
.inner
.stats
.topology_snapshot_publishes
.load(Ordering::Relaxed),
publishes
);
assert_eq!(
allocator
.inner
.stats
.reserved_span_activations
.load(Ordering::Relaxed),
1
);
drop(topology_guard);
for pointer in live {
unsafe { allocator.deallocate(pointer, layout) };
}
}
#[test]
fn aggressive_trim_reclaims_uncommitted_reserved_spans() {
let config = Config {
locality_reserve_spans: 8,
..Config::default()
};
let territory_spans = config.small_territory_spans(17);
let allocator = BoAllocator::new(config).unwrap();
let layout = Layout::from_size_align(4096, 4096).unwrap();
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
let before = allocator.stats();
assert_eq!(before.committed_bytes, SMALL_SPAN_SIZE);
assert_eq!(before.local_free_spans, territory_spans);
let trimmed = allocator.trim(TrimMode::Aggressive);
assert_eq!(trimmed.spans_reclaimed, territory_spans);
assert_eq!(allocator.stats().reserved_bytes, 0);
assert_eq!(allocator.stats().committed_bytes, 0);
}
#[test]
fn trim_reuses_descriptors_after_tls_drops_stale_cache_handles() {
let allocator = BoAllocator::new(Config {
locality_reserve_spans: 2,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(4096, 4096).unwrap();
for _ in 0..32 {
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
allocator.trim(TrimMode::Aggressive);
allocator.with_local_cache(|_| ());
}
let stats = allocator.stats();
assert!(stats.reused_span_descriptors > 0);
assert!(
stats.span_descriptor_slots < 128,
"descriptor high-water mark grew without bound: {}",
stats.span_descriptor_slots
);
allocator.validate().unwrap();
}
#[test]
fn exact_black_pair_keeps_shared_accounting_unchanged() {
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(96, 32).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let seed = allocator.allocate(layout).unwrap();
let seed = NonNull::new(seed.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(seed, layout) };
allocator.synchronize_current_black_accounting();
let pointer = allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert_eq!(magazine.live_delta, 0);
magazine.pointer
});
let span = unsafe { &*pointer };
assert_eq!(span.published_accounting(), (0, 0));
let allocation = allocator.allocate(layout).unwrap();
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert_eq!(magazine.live_delta, 1);
assert_eq!(magazine.requested_delta, 96);
});
assert_eq!(span.published_accounting(), (0, 0));
let allocation = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(allocation, layout) };
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert_eq!(magazine.live_delta, 0);
assert_eq!(magazine.requested_delta, 0);
});
assert_eq!(span.published_accounting(), (0, 0));
allocator.validate().unwrap();
}
#[test]
fn black_span_ring_reuses_cross_span_nursery_frees_and_flushes_on_trim() {
const OBJECTS: usize = 220;
let allocator = BoAllocator::new(Config {
black_span_ring_capacity: 4,
local_magazine_capacity: 8,
remote_cache_capacity: 0,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(1024, 1024).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let first: Vec<_> = (0..OBJECTS)
.map(|_| {
let allocation = allocator.allocate(layout).unwrap();
NonNull::new(allocation.as_ptr() as *mut u8).unwrap()
})
.collect();
let first_addresses: std::collections::HashSet<_> = first
.iter()
.map(|pointer| pointer.as_ptr() as usize)
.collect();
assert_eq!(first_addresses.len(), OBJECTS);
allocator.with_local_cache(|local| {
let class = &local.classes[class_index];
assert!(class.magazine.leased);
assert!((3..=4).contains(&class.black_ring.len));
let ring_bases: std::collections::HashSet<_> = class.black_ring.entries
[..class.black_ring.len]
.iter()
.map(|entry| entry.base)
.collect();
assert_eq!(ring_bases.len(), class.black_ring.len);
let current_base = unsafe { (*class.magazine.pointer).base };
assert!(!ring_bases.contains(¤t_base));
});
for pointer in first.iter().rev().copied() {
unsafe { allocator.deallocate(pointer, layout) };
}
let empty = allocator.stats();
assert_eq!(empty.requested_live_bytes, 0);
assert_eq!(empty.usable_live_bytes, 0);
allocator.with_local_cache(|local| {
let class = &local.classes[class_index];
assert!(
class.black_ring.entries[..class.black_ring.len]
.iter()
.all(|entry| entry.free_len != 0)
);
});
let second: Vec<_> = (0..OBJECTS)
.map(|_| {
let allocation = allocator.allocate(layout).unwrap();
NonNull::new(allocation.as_ptr() as *mut u8).unwrap()
})
.collect();
let second_addresses: std::collections::HashSet<_> = second
.iter()
.map(|pointer| pointer.as_ptr() as usize)
.collect();
assert_eq!(second_addresses.len(), OBJECTS);
assert!(
first_addresses.intersection(&second_addresses).count()
>= OBJECTS - MAX_LOCAL_MAGAZINE_CAPACITY
);
for pointer in second {
unsafe { allocator.deallocate(pointer, layout) };
}
let trimmed = allocator.trim(TrimMode::Aggressive);
assert!(trimmed.spans_reclaimed > 0);
allocator.with_local_cache(|local| {
let class = &local.classes[class_index];
assert_eq!(class.black_ring.len, 0);
assert!(!class.magazine.leased);
});
allocator.validate().unwrap();
}
#[test]
fn remotely_revived_ring_span_transfers_its_existing_lease_to_magazine() {
let allocator = BoAllocator::new(Config {
black_span_ring_capacity: 4,
local_magazine_capacity: 8,
remote_cache_capacity: 0,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(1024, 1024).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let mut live: Vec<_> = (0..130)
.map(|_| {
let allocation = allocator.allocate(layout).unwrap();
NonNull::new(allocation.as_ptr() as *mut u8).unwrap()
})
.collect();
let revived_base = allocator.with_local_cache(|local| {
let ring = &local.classes[class_index].black_ring;
assert_eq!(ring.len, 2);
ring.entries[ring.len - 1].base
});
let remote_index = live
.iter()
.position(|pointer| pointer.as_ptr() as usize & !(SMALL_SPAN_SIZE - 1) == revived_base)
.expect("the retained span still contains a live object");
let remote = live.swap_remove(remote_index).as_ptr() as usize;
let consumer = allocator.clone();
thread::spawn(move || {
let remote = NonNull::new(remote as *mut u8).unwrap();
unsafe { consumer.deallocate(remote, layout) };
})
.join()
.unwrap();
let mut replacements = Vec::new();
let mut promoted = false;
for _ in 0..96 {
let allocation = allocator.allocate(layout).unwrap();
replacements.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
promoted = allocator.with_local_cache(|local| {
let class = &local.classes[class_index];
if !class.magazine.leased {
return false;
}
let current_base = unsafe { (*class.magazine.pointer).base };
if current_base != revived_base {
return false;
}
assert!(
class.black_ring.entries[..class.black_ring.len]
.iter()
.all(|entry| entry.base != revived_base)
);
let distinct: std::collections::HashSet<_> = class.black_ring.entries
[..class.black_ring.len]
.iter()
.map(|entry| entry.base)
.collect();
assert_eq!(distinct.len(), class.black_ring.len);
true
});
if promoted {
break;
}
}
assert!(
promoted,
"the remotely freed slot should revive its retained span"
);
for pointer in live.into_iter().chain(replacements) {
unsafe { allocator.deallocate(pointer, layout) };
}
assert_eq!(allocator.stats().requested_live_bytes, 0);
allocator.trim(TrimMode::Aggressive);
allocator.validate().unwrap();
}
#[test]
fn local_magazine_adapts_without_eager_free_side_refill() {
let allocator = BoAllocator::new(Config {
local_magazine_capacity: 8,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(96, 32).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let first = allocator.allocate(layout).unwrap();
let first = NonNull::new(first.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(first, layout) };
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert_eq!(magazine.len, 1);
assert_eq!(magazine.target, 1);
});
for expected in [1, 2, 4] {
let mut addresses = std::collections::HashSet::new();
let mut pointers = Vec::new();
for _ in 0..expected {
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
assert!(addresses.insert(pointer.as_ptr() as usize));
pointers.push(pointer);
}
if expected == 1 {
assert!(addresses.contains(&(first.as_ptr() as usize)));
}
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert!(magazine.len <= magazine.target);
assert_eq!(magazine.target, (expected * 2).min(8));
});
for pointer in pointers {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert!(magazine.len >= expected);
assert!(magazine.len <= magazine.target);
});
}
let mut addresses = std::collections::HashSet::new();
let mut pointers = Vec::new();
for _ in 0..8 {
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
assert!(addresses.insert(pointer.as_ptr() as usize));
pointers.push(pointer);
}
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert!(magazine.len <= magazine.target);
assert_eq!(magazine.target, 8);
});
for pointer in pointers {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.validate().unwrap();
}
#[test]
fn owner_allocations_refill_magazine_without_local_free() {
let allocator = BoAllocator::new(Config {
local_magazine_capacity: 8,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(96, 32).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
let mut pointers = Vec::new();
for _ in 0..2 {
let allocation = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
}
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert_eq!(magazine.target, 1);
assert_eq!(magazine.len, 1);
});
let third = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(third.as_ptr() as *mut u8).unwrap());
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert_eq!(magazine.target, 2);
assert_eq!(magazine.len, 0);
});
let fourth = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(fourth.as_ptr() as *mut u8).unwrap());
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert_eq!(magazine.target, 2);
assert_eq!(magazine.len, 2);
});
let unique: std::collections::HashSet<_> = pointers
.iter()
.map(|pointer| pointer.as_ptr() as usize)
.collect();
assert_eq!(unique.len(), pointers.len());
assert_eq!(allocator.stats().requested_live_bytes, pointers.len() * 96);
for pointer in pointers {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.validate().unwrap();
}
#[test]
fn owner_local_overflow_reuses_a_large_burst_without_overlap() {
const BURST: usize = 64;
let allocator = BoAllocator::new(Config {
local_magazine_capacity: 8,
..Config::default()
})
.unwrap();
let layout = Layout::from_size_align(96, 32).unwrap();
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
for count in [1, 2, 4, 8] {
let pointers: Vec<_> = (0..count)
.map(|_| {
let allocation = allocator.allocate(layout).unwrap();
NonNull::new(allocation.as_ptr() as *mut u8).unwrap()
})
.collect();
for pointer in pointers {
unsafe { allocator.deallocate(pointer, layout) };
}
}
let first: Vec<_> = (0..BURST)
.map(|_| {
let allocation = allocator.allocate(layout).unwrap();
NonNull::new(allocation.as_ptr() as *mut u8).unwrap()
})
.collect();
let first_addresses: std::collections::HashSet<_> = first
.iter()
.map(|pointer| pointer.as_ptr() as usize)
.collect();
assert_eq!(first_addresses.len(), BURST);
for pointer in first {
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(magazine.leased);
assert_eq!(magazine.target, 8);
assert_eq!(magazine.len, 8);
let span_base = unsafe { (*magazine.pointer).base };
assert!(
magazine.entries[..magazine.len]
.iter()
.all(|address| *address >= span_base
&& *address < span_base + SMALL_SPAN_SIZE
&& *address % layout.align() == 0)
);
assert!(magazine.len + magazine.overflow_len as usize >= BURST);
assert!(first_addresses.contains(&magazine.overflow_head));
});
let second: Vec<_> = (0..(BURST + 7))
.map(|_| {
let allocation = allocator.allocate(layout).unwrap();
NonNull::new(allocation.as_ptr() as *mut u8).unwrap()
})
.collect();
let second_addresses: std::collections::HashSet<_> = second
.iter()
.map(|pointer| pointer.as_ptr() as usize)
.collect();
assert_eq!(second_addresses.len(), BURST + 7);
assert!(first_addresses.is_subset(&second_addresses));
for pointer in second {
unsafe { allocator.deallocate(pointer, layout) };
}
assert_eq!(allocator.stats().requested_live_bytes, 0);
let trimmed = allocator.trim(TrimMode::Aggressive);
assert!(trimmed.spans_reclaimed > 0);
allocator.with_local_cache(|local| {
let magazine = &local.classes[class_index].magazine;
assert!(!magazine.leased);
assert_eq!(magazine.len, 0);
assert_eq!(magazine.overflow_len, 0);
});
allocator.validate().unwrap();
}
#[test]
fn local_magazines_are_independent_per_size_class() {
let allocator = BoAllocator::new(Config {
local_magazine_capacity: 4,
..Config::default()
})
.unwrap();
let layouts = [
Layout::from_size_align(16, 16).unwrap(),
Layout::from_size_align(96, 32).unwrap(),
Layout::from_size_align(1024, 1024).unwrap(),
];
for layout in layouts {
let allocation = allocator.allocate(layout).unwrap();
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();
unsafe { allocator.deallocate(pointer, layout) };
}
allocator.with_local_cache(|local| {
for layout in layouts {
let class_index = allocator
.inner
.config
.class_for(layout.size(), layout.align())
.unwrap();
assert_eq!(local.classes[class_index].magazine.len, 1);
assert_eq!(local.classes[class_index].magazine.target, 1);
assert!(local.classes[class_index].magazine.leased);
}
});
allocator.trim(TrimMode::Aggressive);
allocator.with_local_cache(|local| {
assert!(local.classes.iter().all(|class| {
!class.magazine.leased && class.magazine.len == 0 && class.magazine.target == 0
}));
});
allocator.validate().unwrap();
}
#[test]
fn persistent_run_threads_recover_after_aggressive_trim() {
const THREADS: usize = 8;
const WAVES: usize = 2;
const ALLOCATIONS: usize = 64;
let allocator = BoAllocator::new(Config::default()).unwrap();
let layout = Layout::from_size_align(64 * 1024, 4096).unwrap();
let start = Arc::new(std::sync::Barrier::new(THREADS + 1));
let resume = Arc::new(std::sync::Barrier::new(THREADS + 1));
let (done_sender, done_receiver) = mpsc::channel();
let mut workers = Vec::new();
let progress: Arc<Vec<AtomicUsize>> =
Arc::new((0..THREADS).map(|_| AtomicUsize::new(0)).collect());
for worker_index in 0..THREADS {
let allocator = allocator.clone();
let start = Arc::clone(&start);
let resume = Arc::clone(&resume);
let done_sender = done_sender.clone();
let progress = Arc::clone(&progress);
workers.push(thread::spawn(move || {
for wave in 0..WAVES {
start.wait();
let mut pointers = Vec::with_capacity(ALLOCATIONS);
for allocation_index in 0..ALLOCATIONS {
let allocation = allocator.allocate(layout).unwrap();
pointers.push(NonNull::new(allocation.as_ptr() as *mut u8).unwrap());
progress[worker_index]
.store(wave * 1_000 + allocation_index + 1, Ordering::Release);
}
for pointer in pointers.into_iter().rev() {
unsafe { allocator.deallocate(pointer, layout) };
}
done_sender.send(()).unwrap();
resume.wait();
}
}));
}
drop(done_sender);
for wave in 0..WAVES {
start.wait();
for _ in 0..THREADS {
done_receiver
.recv_timeout(Duration::from_secs(5))
.unwrap_or_else(|_| {
let progress: Vec<_> = progress
.iter()
.map(|value| value.load(Ordering::Acquire))
.collect();
panic!(
"run allocation wave {wave} did not complete: progress={progress:?}, growth={}, claims={}, extent={:#x}, tree_ops={:?}",
allocator.inner.chunk_growth_requested.load(Ordering::Acquire),
allocator.inner.free_claims_in_flight.load(Ordering::Acquire),
allocator.inner.extent_control.load(Ordering::Acquire),
allocator.inner.address_tree.operation_stats(),
)
});
}
allocator.trim(TrimMode::Aggressive);
resume.wait();
}
for worker in workers {
worker.join().unwrap();
}
allocator.validate().unwrap();
}
}