use std::alloc::Layout;
use std::mem::{MaybeUninit, size_of};
use std::ops::Deref;
use std::ptr::NonNull;
use std::sync::atomic::{AtomicU8, AtomicU32, AtomicU64, AtomicUsize, Ordering, fence};
use crate::config::{
ACCOUNTING_TRANSIENT_LIVE_SLACK, MAX_REMOTE_CACHE_CAPACITY, SIZE_CLASSES, SMALL_SPAN_SIZE,
small_payload_offset, small_span_capacity,
};
use crate::os::{release_metadata_block, reserve_commit_metadata_block};
pub(crate) const ANCHOR_MAGIC: u64 = 0x424f_4d41_4c4c_4f43;
pub(crate) const RUN_MAGIC: u64 = 0x424f_5255_4e48_4452;
pub(crate) const NO_CLASS: u8 = u8::MAX;
#[derive(Clone, Copy)]
pub(crate) struct SmallDeallocation;
const BITMAP_ALIGNMENT: usize = 64;
const MAX_BITMAP_WORDS: usize = SMALL_SPAN_SIZE.div_ceil(8).div_ceil(64);
const SPAN_SLOT_BYTES: usize = 256;
const SPANS_PER_METADATA_BLOCK: usize = (64 * 1024) / SPAN_SLOT_BYTES;
const MAX_SPAN_METADATA_BLOCKS: usize = 4096;
const SPAN_FREE_NONE: usize = 0;
const SPAN_FREE_INDEX_BITS: u32 = 21;
const SPAN_FREE_INDEX_MASK: u64 = (1_u64 << SPAN_FREE_INDEX_BITS) - 1;
const BITMAP_CLASS_BYTES: [usize; 5] = [64, 128, 256, 512, 1024];
const MAX_BITMAP_BLOCKS_PER_CLASS: usize = 1024;
const BITMAP_FREE_INDEX_BITS: u32 = 21;
const BITMAP_FREE_INDEX_MASK: u64 = (1_u64 << BITMAP_FREE_INDEX_BITS) - 1;
const STATE_ACTIVE: u8 = 0;
const STATE_FREEZING: u8 = 1;
const STATE_FROZEN: u8 = 2;
const STATE_RETIRED: u8 = 3;
const CONTROL_STATE_MASK: u32 = 0b11;
const CONTROL_FOREIGN_PROBED: u32 = 1 << 2;
const CONTROL_ACTIVE_ONE: u32 = 1 << 3;
const ACCOUNT_LIVE_BITS: u32 = 16;
const ACCOUNT_LIVE_MASK: u64 = (1_u64 << ACCOUNT_LIVE_BITS) - 1;
const _: () = assert!(
(SMALL_SPAN_SIZE / 8) as u64 + ACCOUNTING_TRANSIENT_LIVE_SLACK as u64 <= ACCOUNT_LIVE_MASK
);
const RECYCLED_HINT_LANES: usize = 4;
const INVALID_RECYCLED_HINT: u8 = u8::MAX;
const BLOCK_INDEX_RECIPROCAL_BITS: u32 = 32;
const fn build_block_index_reciprocals() -> [u64; SIZE_CLASSES.len()] {
let mut reciprocals = [0; SIZE_CLASSES.len()];
let mut index = 0;
while index < SIZE_CLASSES.len() {
let divisor = SIZE_CLASSES[index] as u64;
reciprocals[index] = (1_u64 << BLOCK_INDEX_RECIPROCAL_BITS).div_ceil(divisor);
index += 1;
}
reciprocals
}
const BLOCK_INDEX_RECIPROCALS: [u64; SIZE_CLASSES.len()] = build_block_index_reciprocals();
#[inline]
fn exact_block_index(offset: usize, class_index: usize) -> usize {
debug_assert_eq!(offset % SIZE_CLASSES[class_index], 0);
debug_assert!(offset < SMALL_SPAN_SIZE);
((offset as u64 * BLOCK_INDEX_RECIPROCALS[class_index]) >> BLOCK_INDEX_RECIPROCAL_BITS) as usize
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[repr(u8)]
pub(crate) enum SpanKind {
Free = 0,
Small = 1,
Run = 2,
Dedicated = 3,
ReservedSmall = 4,
ReservedRun = 5,
DedicatedReserved = 6,
Retired = 7,
}
impl SpanKind {
pub fn from_raw(value: u8) -> Self {
match value {
0 => Self::Free,
1 => Self::Small,
2 => Self::Run,
3 => Self::Dedicated,
4 => Self::ReservedSmall,
5 => Self::ReservedRun,
6 => Self::DedicatedReserved,
_ => Self::Retired,
}
}
}
#[repr(C, align(64))]
pub(crate) struct SpanAnchor {
pub magic: u64,
pub allocator_id: u64,
pub descriptor: *const SpanDesc,
pub generation: u64,
pub class_index: u64,
_reserved: [u64; 3],
}
impl SpanAnchor {
pub fn new(
allocator_id: u64,
descriptor: *const SpanDesc,
generation: u64,
class_index: usize,
) -> Self {
Self {
magic: ANCHOR_MAGIC,
allocator_id,
descriptor,
generation,
class_index: class_index as u64,
_reserved: [0; 3],
}
}
}
const _: () = assert!(size_of::<SpanAnchor>() == 64);
#[repr(C, align(16))]
pub(crate) struct RunHeader {
pub magic: u64,
pub allocator_id: u64,
pub descriptor: *const SpanDesc,
pub generation: u64,
}
pub(crate) struct RunTerritoryAllocation {
pub user: usize,
pub usable: usize,
pub index: u32,
pub reserved_end: u32,
pub newly_committed: u32,
}
#[repr(align(64))]
pub(crate) struct SpanDesc {
pub base: usize,
pub size: usize,
pub chunk_base: usize,
kind: AtomicU8,
class_index: AtomicU8,
pub generation: AtomicU64,
pub owner: AtomicU64,
pub last_touch: AtomicU64,
control: AtomicU32,
bump: AtomicU32,
accounting: AtomicU64,
capacity: AtomicU32,
usable_live: AtomicUsize,
recycled_hints: AtomicU32,
recycled: AlignedBitmap,
remote_head: AtomicUsize,
foreign_touch: AtomicU64,
foreign_misses: AtomicU64,
}
const COHORT_SEALED_BIT: u64 = 1 << 63;
const COHORT_EPOCH_MASK: u64 = !COHORT_SEALED_BIT;
const DEDICATED_CHARGE_PENDING: u64 = 1;
const DEDICATED_CHARGED_BIT: u64 = 1 << 63;
const DEDICATED_CHARGE_EPOCH_MASK: u64 = !DEDICATED_CHARGED_BIT;
unsafe impl Send for SpanDesc {}
unsafe impl Sync for SpanDesc {}
#[repr(C, align(64))]
struct SpanSlot {
references: AtomicUsize,
next_free: AtomicUsize,
index: usize,
slab: NonNull<SpanSlab>,
descriptor: MaybeUninit<SpanDesc>,
}
const _: () = assert!(size_of::<SpanDesc>() == 192);
const _: () = assert!(size_of::<SpanSlot>() == SPAN_SLOT_BYTES);
const _: () = assert!(std::mem::offset_of!(SpanSlot, descriptor) == 64);
struct BitmapClass {
blocks: [AtomicUsize; MAX_BITMAP_BLOCKS_PER_CLASS],
next: AtomicUsize,
free_head: AtomicU64,
reused: AtomicU64,
}
impl BitmapClass {
fn new() -> Self {
Self {
blocks: std::array::from_fn(|_| AtomicUsize::new(0)),
next: AtomicUsize::new(0),
free_head: AtomicU64::new(0),
reused: AtomicU64::new(0),
}
}
}
struct BitmapSlab {
classes: [BitmapClass; BITMAP_CLASS_BYTES.len()],
live: AtomicUsize,
}
impl BitmapSlab {
fn new() -> Self {
Self {
classes: std::array::from_fn(|_| BitmapClass::new()),
live: AtomicUsize::new(0),
}
}
fn class_for(words: usize) -> usize {
let bytes = words
.checked_mul(size_of::<AtomicU64>())
.expect("small-span bitmap size overflow")
.max(BITMAP_ALIGNMENT)
.next_power_of_two();
BITMAP_CLASS_BYTES
.iter()
.position(|class_bytes| bytes <= *class_bytes)
.expect("small-span bitmap exceeds its 1 KiB design bound")
}
fn slots_per_block(class_index: usize) -> usize {
(64 * 1024) / BITMAP_CLASS_BYTES[class_index]
}
fn block(&self, class_index: usize, block_index: usize) -> usize {
assert!(
block_index < MAX_BITMAP_BLOCKS_PER_CLASS,
"small-span bitmap slab exhausted"
);
let class = &self.classes[class_index];
let current = class.blocks[block_index].load(Ordering::Acquire);
if current != 0 {
return current;
}
let candidate = unsafe { reserve_commit_metadata_block(64 * 1024) }
.unwrap_or_else(|error| panic!("unable to reserve bitmap metadata block: {error}"));
match class.blocks[block_index].compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
let _ = unsafe { release_metadata_block(candidate) };
installed
}
}
}
fn pointer(&self, class_index: usize, index: usize) -> NonNull<AtomicU64> {
let slots_per_block = Self::slots_per_block(class_index);
let block = self.block(class_index, index / slots_per_block);
let address = block + (index % slots_per_block) * BITMAP_CLASS_BYTES[class_index];
unsafe { NonNull::new_unchecked(address as *mut AtomicU64) }
}
fn pop_free(&self, class_index: usize) -> Option<usize> {
let class = &self.classes[class_index];
let mut head = class.free_head.load(Ordering::Acquire);
loop {
let encoded = (head & BITMAP_FREE_INDEX_MASK) as usize;
if encoded == 0 {
return None;
}
let index = encoded - 1;
let pointer = self.pointer(class_index, index);
let next = unsafe { pointer.as_ref() }.load(Ordering::Acquire) as usize;
let tag = (head >> BITMAP_FREE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << BITMAP_FREE_INDEX_BITS) | next as u64;
match class.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(index),
Err(actual) => head = actual,
}
}
}
fn push_free(&self, class_index: usize, index: usize, pointer: NonNull<AtomicU64>) {
let encoded = index.checked_add(1).expect("bitmap slab index overflow");
assert!(encoded <= BITMAP_FREE_INDEX_MASK as usize);
let class = &self.classes[class_index];
let mut head = class.free_head.load(Ordering::Acquire);
loop {
unsafe { pointer.as_ref() }.store(head & BITMAP_FREE_INDEX_MASK, Ordering::Release);
let tag = (head >> BITMAP_FREE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << BITMAP_FREE_INDEX_BITS) | encoded as u64;
match class.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return,
Err(actual) => head = actual,
}
}
}
fn allocate(&self, bitmap_words: usize) -> AlignedBitmap {
if bitmap_words == 0 {
return AlignedBitmap::pending(0);
}
let class_index = Self::class_for(bitmap_words);
let class = &self.classes[class_index];
let reused = self.pop_free(class_index);
let index = reused.unwrap_or_else(|| class.next.fetch_add(1, Ordering::AcqRel));
let pointer = self.pointer(class_index, index);
for word in 0..bitmap_words {
unsafe { pointer.as_ptr().add(word).write(AtomicU64::new(0)) };
}
if reused.is_some() {
class.reused.fetch_add(1, Ordering::Relaxed);
}
self.live.fetch_add(1, Ordering::Relaxed);
AlignedBitmap {
pointer,
len: bitmap_words,
slab: Some(NonNull::from(self)),
index,
class_index: class_index as u8,
}
}
fn allocated_blocks(&self) -> usize {
self.classes
.iter()
.flat_map(|class| class.blocks.iter())
.filter(|block| block.load(Ordering::Acquire) != 0)
.count()
}
fn reused(&self) -> u64 {
self.classes
.iter()
.map(|class| class.reused.load(Ordering::Relaxed))
.sum()
}
fn slots(&self) -> usize {
self.classes
.iter()
.map(|class| class.next.load(Ordering::Relaxed))
.sum()
}
fn live(&self) -> usize {
self.live.load(Ordering::Relaxed)
}
}
impl Drop for BitmapSlab {
fn drop(&mut self) {
for class in &self.classes {
for block in &class.blocks {
let address = block.load(Ordering::Relaxed);
if address != 0 {
let _ = unsafe { release_metadata_block(address) };
}
}
}
}
}
struct SpanSlab {
blocks: [AtomicUsize; MAX_SPAN_METADATA_BLOCKS],
bitmaps: BitmapSlab,
lifetime_references: AtomicUsize,
next: AtomicUsize,
free_head: AtomicU64,
live: AtomicUsize,
reused: AtomicU64,
}
impl SpanSlab {
fn new() -> Self {
Self {
blocks: std::array::from_fn(|_| AtomicUsize::new(0)),
bitmaps: BitmapSlab::new(),
lifetime_references: AtomicUsize::new(1),
next: AtomicUsize::new(0),
free_head: AtomicU64::new(0),
live: AtomicUsize::new(0),
reused: AtomicU64::new(0),
}
}
fn block(&self, block_index: usize) -> usize {
let current = self.blocks[block_index].load(Ordering::Acquire);
if current != 0 {
return current;
}
let candidate = unsafe { reserve_commit_metadata_block(64 * 1024) }
.unwrap_or_else(|error| panic!("unable to reserve SpanDesc metadata block: {error}"));
for offset in 0..SPANS_PER_METADATA_BLOCK {
let slot = (candidate + offset * SPAN_SLOT_BYTES) as *mut SpanSlot;
unsafe {
slot.write(SpanSlot {
references: AtomicUsize::new(0),
next_free: AtomicUsize::new(SPAN_FREE_NONE),
index: block_index * SPANS_PER_METADATA_BLOCK + offset,
slab: NonNull::from(self),
descriptor: MaybeUninit::uninit(),
})
};
}
match self.blocks[block_index].compare_exchange(
0,
candidate,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => candidate,
Err(installed) => {
let _ = unsafe { release_metadata_block(candidate) };
installed
}
}
}
fn slot(&self, index: usize) -> &SpanSlot {
let block_index = index / SPANS_PER_METADATA_BLOCK;
assert!(
block_index < MAX_SPAN_METADATA_BLOCKS,
"SpanDesc metadata slab exhausted"
);
let block = self.block(block_index);
let offset = index % SPANS_PER_METADATA_BLOCK;
unsafe { &*((block + offset * SPAN_SLOT_BYTES) as *const SpanSlot) }
}
fn pop_free(&self) -> Option<usize> {
let mut head = self.free_head.load(Ordering::Acquire);
loop {
let encoded = (head & SPAN_FREE_INDEX_MASK) as usize;
if encoded == SPAN_FREE_NONE {
return None;
}
let index = encoded - 1;
let next = self.slot(index).next_free.load(Ordering::Acquire);
let tag = (head >> SPAN_FREE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << SPAN_FREE_INDEX_BITS) | next as u64;
match self.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(index),
Err(actual) => head = actual,
}
}
}
fn push_free(&self, index: usize) {
let encoded = index.checked_add(1).expect("SpanDesc slab index overflow");
assert!(encoded <= SPAN_FREE_INDEX_MASK as usize);
let slot = self.slot(index);
let mut head = self.free_head.load(Ordering::Acquire);
loop {
slot.next_free
.store((head & SPAN_FREE_INDEX_MASK) as usize, Ordering::Release);
let tag = (head >> SPAN_FREE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << SPAN_FREE_INDEX_BITS) | encoded as u64;
match self.free_head.compare_exchange_weak(
head,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return,
Err(actual) => head = actual,
}
}
}
fn allocate(&self, mut descriptor: SpanDesc) -> SpanHandle {
descriptor.attach_bitmap(&self.bitmaps);
let reused = self.pop_free();
let index = reused.unwrap_or_else(|| self.next.fetch_add(1, Ordering::AcqRel));
let slot = self.slot(index);
assert_eq!(slot.references.load(Ordering::Acquire), 0);
unsafe { (slot.descriptor.as_ptr() as *mut SpanDesc).write(descriptor) };
let lifetime = self.lifetime_references.fetch_add(1, Ordering::Relaxed);
assert!(lifetime != 0 && lifetime < usize::MAX / 2);
slot.references.store(1, Ordering::Release);
self.live.fetch_add(1, Ordering::Relaxed);
if reused.is_some() {
self.reused.fetch_add(1, Ordering::Relaxed);
}
SpanHandle {
descriptor: NonNull::from(unsafe { &*slot.descriptor.as_ptr() }),
}
}
unsafe fn release_lifetime(slab: NonNull<Self>) {
let slab_ref = unsafe { slab.as_ref() };
if slab_ref.lifetime_references.fetch_sub(1, Ordering::Release) != 1 {
return;
}
fence(Ordering::Acquire);
unsafe { drop(Box::from_raw(slab.as_ptr())) };
}
fn allocated_blocks(&self) -> usize {
self.blocks
.iter()
.filter(|block| block.load(Ordering::Acquire) != 0)
.count()
+ self.bitmaps.allocated_blocks()
}
}
impl Drop for SpanSlab {
fn drop(&mut self) {
debug_assert_eq!(self.live.load(Ordering::Relaxed), 0);
for block in &self.blocks {
let address = block.load(Ordering::Relaxed);
if address != 0 {
let _ = unsafe { release_metadata_block(address) };
}
}
}
}
pub(crate) struct SpanSlabOwner {
slab: NonNull<SpanSlab>,
}
unsafe impl Send for SpanSlabOwner {}
unsafe impl Sync for SpanSlabOwner {}
impl SpanSlabOwner {
pub fn new() -> Self {
let slab = Box::new(SpanSlab::new());
Self {
slab: unsafe { NonNull::new_unchecked(Box::into_raw(slab)) },
}
}
pub fn allocate(&self, descriptor: SpanDesc) -> SpanHandle {
self.slab().allocate(descriptor)
}
pub fn allocated_blocks(&self) -> usize {
self.slab().allocated_blocks()
}
pub fn slots(&self) -> usize {
self.slab().next.load(Ordering::Relaxed)
}
pub fn live(&self) -> usize {
self.slab().live.load(Ordering::Relaxed)
}
pub fn reused(&self) -> u64 {
self.slab().reused.load(Ordering::Relaxed)
}
pub fn bitmap_slots(&self) -> usize {
self.slab().bitmaps.slots()
}
pub fn live_bitmaps(&self) -> usize {
self.slab().bitmaps.live()
}
pub fn reused_bitmaps(&self) -> u64 {
self.slab().bitmaps.reused()
}
pub fn control_bytes(&self) -> usize {
size_of::<SpanSlab>()
}
fn slab(&self) -> &SpanSlab {
unsafe { self.slab.as_ref() }
}
}
impl Drop for SpanSlabOwner {
fn drop(&mut self) {
unsafe { SpanSlab::release_lifetime(self.slab) };
}
}
pub(crate) struct SpanHandle {
descriptor: NonNull<SpanDesc>,
}
unsafe impl Send for SpanHandle {}
unsafe impl Sync for SpanHandle {}
impl SpanHandle {
pub fn as_ptr(&self) -> *const SpanDesc {
self.descriptor.as_ptr()
}
pub fn ptr_eq(left: &Self, right: &Self) -> bool {
left.descriptor == right.descriptor
}
fn slot(&self) -> &SpanSlot {
let address = self.descriptor.as_ptr() as usize - 64;
unsafe { &*(address as *const SpanSlot) }
}
}
impl Clone for SpanHandle {
fn clone(&self) -> Self {
let previous = self.slot().references.fetch_add(1, Ordering::Relaxed);
assert!(previous != 0 && previous < usize::MAX / 2);
Self {
descriptor: self.descriptor,
}
}
}
impl Deref for SpanHandle {
type Target = SpanDesc;
fn deref(&self) -> &Self::Target {
unsafe { self.descriptor.as_ref() }
}
}
impl Drop for SpanHandle {
fn drop(&mut self) {
let slot = self.slot();
if slot.references.fetch_sub(1, Ordering::Release) != 1 {
return;
}
fence(Ordering::Acquire);
unsafe { std::ptr::drop_in_place(self.descriptor.as_ptr()) };
let slab = unsafe { slot.slab.as_ref() };
slab.live.fetch_sub(1, Ordering::Relaxed);
slab.push_free(slot.index);
unsafe { SpanSlab::release_lifetime(slot.slab) };
}
}
struct AlignedBitmap {
pointer: NonNull<AtomicU64>,
len: usize,
slab: Option<NonNull<BitmapSlab>>,
index: usize,
class_index: u8,
}
unsafe impl Send for AlignedBitmap {}
unsafe impl Sync for AlignedBitmap {}
impl AlignedBitmap {
fn pending(len: usize) -> Self {
Self {
pointer: NonNull::dangling(),
len,
slab: None,
index: 0,
class_index: 0,
}
}
fn len(&self) -> usize {
self.len
}
fn get(&self, index: usize) -> &AtomicU64 {
assert!(index < self.len);
assert!(self.slab.is_some(), "SpanDesc bitmap was not slab-attached");
unsafe { &*self.pointer.as_ptr().add(index) }
}
fn iter(&self) -> impl Iterator<Item = &AtomicU64> {
(0..self.len).map(|index| self.get(index))
}
}
impl Drop for AlignedBitmap {
fn drop(&mut self) {
if let Some(slab) = self.slab {
let slab = unsafe { slab.as_ref() };
slab.push_free(self.class_index as usize, self.index, self.pointer);
slab.live.fetch_sub(1, Ordering::Relaxed);
}
}
}
impl SpanDesc {
pub fn free(base: usize, size: usize, chunk_base: usize) -> Self {
Self::new(base, size, chunk_base, SpanKind::Free, NO_CLASS, 0)
}
fn attach_bitmap(&mut self, slab: &BitmapSlab) {
if self.recycled.len == 0 {
return;
}
assert!(self.recycled.slab.is_none());
self.recycled = slab.allocate(self.recycled.len);
}
pub fn small(base: usize, chunk_base: usize, class_index: usize, block_size: usize) -> Self {
debug_assert_eq!(block_size, SIZE_CLASSES[class_index]);
let capacity = small_span_capacity(class_index) as u32;
Self::new(
base,
SMALL_SPAN_SIZE,
chunk_base,
SpanKind::Small,
class_index as u8,
capacity,
)
}
pub fn reserved_small(
base: usize,
chunk_base: usize,
class_index: usize,
block_size: usize,
) -> Self {
debug_assert_eq!(block_size, SIZE_CLASSES[class_index]);
let capacity = small_span_capacity(class_index) as u32;
Self::new(
base,
SMALL_SPAN_SIZE,
chunk_base,
SpanKind::ReservedSmall,
class_index as u8,
capacity,
)
}
pub fn run(base: usize, size: usize, chunk_base: usize, dedicated: bool) -> Self {
Self::new(
base,
size,
chunk_base,
if dedicated {
SpanKind::Dedicated
} else {
SpanKind::Run
},
NO_CLASS,
1,
)
}
pub fn run_territory(
base: usize,
size: usize,
chunk_base: usize,
extent_size: usize,
capacity: u32,
) -> Self {
debug_assert!(capacity > 1);
debug_assert_eq!(size, extent_size * capacity as usize);
let descriptor = Self::new(base, size, chunk_base, SpanKind::Run, NO_CLASS, capacity);
descriptor.remote_head.store(extent_size, Ordering::Relaxed);
descriptor
}
pub fn reserved_run(base: usize, size: usize, chunk_base: usize) -> Self {
Self::new(base, size, chunk_base, SpanKind::ReservedRun, NO_CLASS, 1)
}
fn new(
base: usize,
size: usize,
chunk_base: usize,
kind: SpanKind,
class_index: u8,
capacity: u32,
) -> Self {
let bitmap_words = (capacity as usize).div_ceil(64);
Self {
base,
size,
chunk_base,
kind: AtomicU8::new(kind as u8),
class_index: AtomicU8::new(class_index),
generation: AtomicU64::new(1),
owner: AtomicU64::new(0),
last_touch: AtomicU64::new(0),
control: AtomicU32::new(STATE_ACTIVE as u32),
bump: AtomicU32::new(0),
accounting: AtomicU64::new(0),
capacity: AtomicU32::new(capacity),
usable_live: AtomicUsize::new(0),
recycled_hints: AtomicU32::new(u32::MAX),
recycled: AlignedBitmap::pending(bitmap_words),
remote_head: AtomicUsize::new(0),
foreign_touch: AtomicU64::new(0),
foreign_misses: AtomicU64::new(0),
}
}
pub fn kind(&self) -> SpanKind {
SpanKind::from_raw(self.kind.load(Ordering::Acquire))
}
pub fn is_run_territory(&self) -> bool {
self.kind() == SpanKind::Run && self.capacity() > 1
}
pub fn run_extent_size(&self) -> Option<usize> {
self.is_run_territory()
.then(|| self.remote_head.load(Ordering::Relaxed))
}
pub fn run_high_water(&self) -> u32 {
self.bump.load(Ordering::Acquire)
}
fn state(&self) -> u8 {
control_state(self.control.load(Ordering::Acquire))
}
fn transition_control_state(&self, expected: u8, replacement: u8) -> bool {
let mut control = self.control.load(Ordering::Acquire);
loop {
if control_state(control) != expected {
return false;
}
let replacement = (control & !CONTROL_STATE_MASK) | replacement as u32;
match self.control.compare_exchange_weak(
control,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return true,
Err(actual) => control = actual,
}
}
}
pub fn is_available_free(&self) -> bool {
self.kind() == SpanKind::Free && self.state() == STATE_ACTIVE
}
pub fn try_claim_free(&self) -> bool {
if self.kind() != SpanKind::Free || !self.try_freeze_empty() {
return false;
}
if self.kind() == SpanKind::Free {
true
} else {
self.unfreeze();
false
}
}
pub fn class_index(&self) -> Option<usize> {
let value = self.class_index.load(Ordering::Relaxed);
(value != NO_CLASS).then_some(value as usize)
}
pub fn live(&self) -> u32 {
accounting_live(self.current_accounting())
}
#[inline(always)]
pub fn capacity(&self) -> u32 {
self.capacity.load(Ordering::Relaxed)
}
pub fn requested_live(&self) -> usize {
accounting_requested(self.current_accounting())
}
#[cfg(test)]
pub(crate) fn published_accounting(&self) -> (u32, usize) {
let accounting = self.accounting.load(Ordering::Acquire);
(
accounting_live(accounting),
accounting_requested(accounting),
)
}
pub fn usable_live(&self) -> usize {
if let Some(class_index) = self.class_index() {
self.live() as usize * crate::config::SIZE_CLASSES[class_index]
} else {
self.usable_live.load(Ordering::Relaxed)
}
}
pub fn has_capacity(&self) -> bool {
if self.kind() != SpanKind::Small || self.state() != STATE_ACTIVE || self.is_cohort_sealed()
{
return false;
}
if self.bump.load(Ordering::Relaxed) < self.capacity() {
return true;
}
self.recycled
.iter()
.any(|word| word.load(Ordering::Relaxed) != 0)
|| self.remote_head.load(Ordering::Relaxed) != 0
}
fn try_enter(&self) -> Option<ActiveOp<'_>> {
let mut control = self.control.load(Ordering::Acquire);
loop {
if control_state(control) != STATE_ACTIVE {
return None;
}
debug_assert!(control <= u32::MAX - CONTROL_ACTIVE_ONE);
match self.control.compare_exchange_weak(
control,
control + CONTROL_ACTIVE_ONE,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => {
if control & CONTROL_FOREIGN_PROBED != 0 {
self.clear_foreign_probe();
}
return Some(ActiveOp(self));
}
Err(actual) => control = actual,
}
}
}
#[cold]
#[inline(never)]
fn clear_foreign_probe(&self) {
if self
.control
.fetch_and(!CONTROL_FOREIGN_PROBED, Ordering::AcqRel)
& CONTROL_FOREIGN_PROBED
!= 0
{
if self.kind() != SpanKind::Small {
self.last_touch.fetch_add(1, Ordering::Relaxed);
}
self.foreign_misses.store(0, Ordering::Relaxed);
}
}
fn try_enter_deallocate(&self) -> Option<ActiveOp<'_>> {
let mut control = self.control.load(Ordering::Acquire);
loop {
let state = control_state(control);
if state != STATE_ACTIVE && !(state == STATE_FREEZING && self.live() != 0) {
return None;
}
debug_assert!(control <= u32::MAX - CONTROL_ACTIVE_ONE);
match self.control.compare_exchange_weak(
control,
control + CONTROL_ACTIVE_ONE,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(ActiveOp(self)),
Err(actual) => control = actual,
}
}
}
pub fn try_acquire_local_cache_lease(
&self,
owner: u64,
generation: u64,
class_index: usize,
) -> bool {
let mut control = self.control.load(Ordering::Acquire);
loop {
if control_state(control) != STATE_ACTIVE {
return false;
}
debug_assert!(control <= u32::MAX - CONTROL_ACTIVE_ONE);
match self.control.compare_exchange_weak(
control,
control + CONTROL_ACTIVE_ONE,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => control = actual,
}
}
let valid = self.kind() == SpanKind::Small
&& !self.is_cohort_sealed()
&& self.class_index() == Some(class_index)
&& self.owner.load(Ordering::Acquire) == owner
&& self.generation.load(Ordering::Acquire) == generation;
if !valid {
self.release_local_cache_lease();
} else if control & CONTROL_FOREIGN_PROBED != 0 {
self.clear_foreign_probe();
}
valid
}
pub fn release_local_cache_lease(&self) {
let previous = self
.control
.fetch_sub(CONTROL_ACTIVE_ONE, Ordering::Release);
debug_assert_ne!(active_operations(previous), 0);
}
#[inline]
pub unsafe fn allocate_local_cached_address(
&self,
owner: u64,
generation: u64,
class_index: usize,
address: usize,
) -> usize {
debug_assert_eq!(self.kind(), SpanKind::Small);
debug_assert!(!self.is_cohort_sealed());
debug_assert_eq!(self.class_index(), Some(class_index));
debug_assert_eq!(self.owner.load(Ordering::Acquire), owner);
debug_assert_eq!(self.generation.load(Ordering::Acquire), generation);
let class_size = crate::config::SIZE_CLASSES[class_index];
let payload = self.base + small_payload_offset(class_index);
let offset = address.wrapping_sub(payload);
debug_assert_eq!(offset % class_size, 0);
debug_assert!(
exact_block_index(offset, class_index) < self.bump.load(Ordering::Acquire) as usize
);
address
}
pub fn try_allocate_small_leased(
&self,
class_index: usize,
owner: u64,
generation: u64,
recent_free_word_hints: usize,
) -> Option<(usize, u32)> {
debug_assert_eq!(self.kind(), SpanKind::Small);
debug_assert!(!self.is_cohort_sealed());
debug_assert_eq!(self.class_index(), Some(class_index));
debug_assert_eq!(self.owner.load(Ordering::Acquire), owner);
debug_assert_eq!(self.generation.load(Ordering::Acquire), generation);
self.try_allocate_small_slot(class_index, recent_free_word_hints)
}
pub fn reserve_small_for_local_cache(
&self,
class_index: usize,
owner: u64,
generation: u64,
recent_free_word_hints: usize,
) -> Option<(usize, u32)> {
if self.kind() != SpanKind::Small
|| self.is_cohort_sealed()
|| self.class_index() != Some(class_index)
|| self.owner.load(Ordering::Acquire) != owner
|| self.generation.load(Ordering::Acquire) != generation
{
return None;
}
let (address, remote_drained) =
self.try_allocate_small_slot(class_index, recent_free_word_hints)?;
Some((address, remote_drained))
}
#[inline]
pub unsafe fn deallocate_small_to_local_cache(
&self,
address: usize,
owner: u64,
generation: u64,
class_index: usize,
) -> usize {
debug_assert_eq!(self.kind(), SpanKind::Small);
debug_assert_eq!(self.class_index(), Some(class_index));
debug_assert_eq!(self.owner.load(Ordering::Acquire), owner);
debug_assert_eq!(self.generation.load(Ordering::Acquire), generation);
let class_size = crate::config::SIZE_CLASSES[class_index];
let payload = self.base + small_payload_offset(class_index);
let offset = address.wrapping_sub(payload);
debug_assert_eq!(offset % class_size, 0);
debug_assert!(
exact_block_index(offset, class_index) < self.bump.load(Ordering::Acquire) as usize
);
address
}
pub fn publish_local_cached_index(&self, index: u32, recent_free_word_hints: usize) {
debug_assert!(index < self.bump.load(Ordering::Acquire));
let word_index = index as usize / 64;
let mask = 1_u64 << (index % 64);
let previous = self
.recycled
.get(word_index)
.fetch_or(mask, Ordering::Release);
debug_assert_eq!(previous & mask, 0, "local cached block published twice");
self.record_recycled_word(word_index, recent_free_word_hints);
}
pub fn publish_local_cached_address(&self, address: usize, recent_free_word_hints: usize) {
let class_index = self
.class_index()
.expect("a local cached block belongs to a small span");
let payload = self.base + small_payload_offset(class_index);
let offset = address.wrapping_sub(payload);
debug_assert_eq!(offset % crate::config::SIZE_CLASSES[class_index], 0);
let index = exact_block_index(offset, class_index) as u32;
self.publish_local_cached_index(index, recent_free_word_hints);
}
pub fn try_allocate_small(
&self,
class_index: usize,
layout: Layout,
owner: u64,
generation: u64,
recent_free_word_hints: usize,
) -> Option<(usize, u32)> {
let _active = self.try_enter()?;
if self.kind() != SpanKind::Small
|| self.is_cohort_sealed()
|| self.class_index() != Some(class_index)
|| self.owner.load(Ordering::Acquire) != owner
|| self.generation.load(Ordering::Acquire) != generation
{
return None;
}
let result = self.try_allocate_small_slot(class_index, recent_free_word_hints)?;
self.account_small_allocation(layout);
Some(result)
}
fn try_allocate_small_slot(
&self,
class_index: usize,
recent_free_word_hints: usize,
) -> Option<(usize, u32)> {
let class_size = crate::config::SIZE_CLASSES[class_index];
if let Some(address) = self.try_claim_recycled_hints(class_size, recent_free_word_hints) {
return Some((address, 0));
}
let index = self.bump.load(Ordering::Relaxed);
let capacity = self.capacity();
if index < capacity {
self.bump.store(index + 1, Ordering::Relaxed);
return Some((self.finish_small_allocation(index, class_size), 0));
}
if let Some(address) = self.try_claim_recycled(class_size, recent_free_word_hints) {
return Some((address, 0));
}
let drained = self.drain_remote_frees(recent_free_word_hints);
let address = self.try_claim_recycled(class_size, recent_free_word_hints)?;
Some((address, drained))
}
#[inline]
fn account_small_allocation(&self, layout: Layout) {
let current = self.fold_remote_accounting();
debug_assert!(accounting_live(current) < self.capacity() + ACCOUNTING_TRANSIENT_LIVE_SLACK);
let next = current + pack_accounting(1, layout.size());
self.accounting.store(next, Ordering::Release);
}
#[cfg(test)]
fn account_small_owner_deallocation(&self, layout: Layout) {
let current = self.accounting.load(Ordering::Acquire);
debug_assert_ne!(accounting_live(current), 0);
debug_assert!(accounting_requested(current) >= layout.size());
self.accounting.store(
current - pack_accounting(1, layout.size()),
Ordering::Release,
);
}
fn account_small_remote_deallocation(&self, layout: Layout) {
let delta = pack_accounting(1, layout.size()) as usize;
let capacity = self.capacity();
let previous = self.usable_live.fetch_add(delta, Ordering::AcqRel) as u64;
debug_assert!(
accounting_live(previous) < capacity + ACCOUNTING_TRANSIENT_LIVE_SLACK,
"the packed remote live counter exceeded its transient slack"
);
}
pub(crate) unsafe fn publish_remote_cached_batch(
&self,
addresses: &[usize],
requested: &[u16],
class_index: usize,
) {
debug_assert_eq!(addresses.len(), requested.len());
debug_assert!(!addresses.is_empty());
debug_assert!(addresses.len() <= MAX_REMOTE_CACHE_CAPACITY);
let payload = self.base + small_payload_offset(class_index);
let mut word_indices = [0_usize; MAX_REMOTE_CACHE_CAPACITY];
let mut masks = [0_u64; MAX_REMOTE_CACHE_CAPACITY];
let mut word_count = 0;
for address in addresses.iter().copied() {
let offset = address - payload;
let index = exact_block_index(offset, class_index);
debug_assert_eq!(offset % SIZE_CLASSES[class_index], 0);
debug_assert!(index < self.bump.load(Ordering::Relaxed) as usize);
let word_index = index / 64;
let mask = 1_u64 << (index % 64);
if let Some(slot) = word_indices[..word_count]
.iter()
.position(|candidate| *candidate == word_index)
{
debug_assert_eq!(masks[slot] & mask, 0, "duplicate cached remote free");
masks[slot] |= mask;
} else {
word_indices[word_count] = word_index;
masks[word_count] = mask;
word_count += 1;
}
}
for slot in 0..word_count {
let previous = self
.recycled
.get(word_indices[slot])
.fetch_or(masks[slot], Ordering::Release);
debug_assert_eq!(previous & masks[slot], 0, "double free detected");
}
let requested = requested.iter().map(|value| *value as usize).sum();
let delta = pack_accounting(addresses.len() as u32, requested) as usize;
self.usable_live.fetch_add(delta, Ordering::AcqRel);
}
#[inline]
fn fold_remote_accounting(&self) -> u64 {
let observed = self.usable_live.load(Ordering::Acquire) as u64;
let remote = if observed == 0 {
0
} else {
self.usable_live.swap(0, Ordering::AcqRel) as u64
};
let owned = self.accounting.load(Ordering::Acquire);
debug_assert!(accounting_live(owned) >= accounting_live(remote));
debug_assert!(accounting_requested(owned) >= accounting_requested(remote));
subtract_accounting(owned, remote)
}
pub(crate) fn synchronize_remote_accounting(&self) {
self.accounting
.store(self.fold_remote_accounting(), Ordering::Release);
}
pub(crate) fn synchronize_local_cache_accounting(&self, live_delta: i32, requested_delta: i64) {
let remote = self.usable_live.swap(0, Ordering::AcqRel) as u64;
let owned = self.accounting.load(Ordering::Acquire);
let next_live =
accounting_live(owned) as i64 + live_delta as i64 - accounting_live(remote) as i64;
let next_requested = accounting_requested(owned) as i128 + requested_delta as i128
- accounting_requested(remote) as i128;
debug_assert!(next_live >= 0);
debug_assert!(next_requested >= 0);
debug_assert!(next_live as u64 <= ACCOUNT_LIVE_MASK);
self.accounting.store(
pack_accounting(next_live.max(0) as u32, next_requested.max(0) as usize),
Ordering::Release,
);
}
fn current_accounting(&self) -> u64 {
if self.class_index.load(Ordering::Relaxed) == NO_CLASS {
self.accounting.load(Ordering::Acquire)
} else {
let remote = self.usable_live.load(Ordering::Acquire) as u64;
let owned = self.accounting.load(Ordering::Acquire);
saturating_subtract_accounting(owned, remote)
}
}
fn try_claim_recycled_hints(&self, class_size: usize, hint_count: usize) -> Option<usize> {
let word_count = self.recycled.len();
if word_count == 0 {
return None;
}
let packed = self.recycled_hints.load(Ordering::Relaxed);
let checked_lanes = hint_count.min(RECYCLED_HINT_LANES);
for lane in 0..checked_lanes {
let shift = lane * 8;
let word_index = ((packed >> shift) & 0xff) as u8;
if word_index == INVALID_RECYCLED_HINT || word_index as usize >= word_count {
continue;
}
if let Some(address) = self.try_claim_recycled_word(word_index as usize, class_size) {
let retain = (self
.recycled
.get(word_index as usize)
.load(Ordering::Acquire)
!= 0)
.then_some(word_index as usize);
self.compact_recycled_hints(packed, lane + 1, retain, hint_count);
return Some(address);
}
}
self.compact_recycled_hints(packed, checked_lanes, None, hint_count);
None
}
fn compact_recycled_hints(
&self,
current: u32,
consumed_lanes: usize,
retain_word: Option<usize>,
hint_count: usize,
) {
let mut packed = u32::MAX;
let mut target_lane = 0;
if let Some(word_index) = retain_word {
packed = (packed & !0xff) | word_index as u32;
target_lane = 1;
}
for lane in consumed_lanes..RECYCLED_HINT_LANES {
if target_lane == hint_count.min(RECYCLED_HINT_LANES) {
break;
}
let candidate = ((current >> (lane * 8)) & 0xff) as u8;
if candidate == INVALID_RECYCLED_HINT
|| retain_word.is_some_and(|word| word == candidate as usize)
{
continue;
}
let shift = target_lane * 8;
packed = (packed & !(0xff << shift)) | (candidate as u32) << shift;
target_lane += 1;
}
self.recycled_hints.store(packed, Ordering::Relaxed);
}
fn try_claim_recycled(
&self,
class_size: usize,
recent_free_word_hints: usize,
) -> Option<usize> {
let word_count = self.recycled.len();
if word_count != 0 {
let newest = self.recycled_hints.load(Ordering::Relaxed) as u8;
let start = if newest == INVALID_RECYCLED_HINT {
0
} else {
newest as usize % word_count
};
for offset in 0..word_count {
let word_index = (start + offset) % word_count;
if let Some(address) = self.try_claim_recycled_word(word_index, class_size) {
if self.recycled.get(word_index).load(Ordering::Acquire) != 0 {
self.record_recycled_word(word_index, recent_free_word_hints);
}
return Some(address);
}
}
}
None
}
fn try_claim_recycled_word(&self, word_index: usize, class_size: usize) -> Option<usize> {
let capacity = self.capacity();
let word = self.recycled.get(word_index);
let mut current = word.load(Ordering::Acquire);
while current != 0 {
let bit = current.trailing_zeros();
let index = word_index as u32 * 64 + bit;
if index >= capacity {
break;
}
let mask = 1_u64 << bit;
match word.compare_exchange_weak(
current,
current & !mask,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => {
return Some(self.finish_small_allocation(index, class_size));
}
Err(actual) => current = actual,
}
}
None
}
fn record_recycled_word(&self, word_index: usize, hint_count: usize) {
debug_assert!(word_index < INVALID_RECYCLED_HINT as usize);
let hint_count = hint_count.min(RECYCLED_HINT_LANES);
if hint_count == 0 {
return;
}
let current = self.recycled_hints.load(Ordering::Relaxed);
let mut packed = word_index as u32;
let mut target_lane = 1;
for lane in 0..RECYCLED_HINT_LANES {
if target_lane == hint_count {
break;
}
let candidate = ((current >> (lane * 8)) & 0xff) as u8;
if candidate == INVALID_RECYCLED_HINT || candidate as usize == word_index {
continue;
}
packed |= (candidate as u32) << (target_lane * 8);
target_lane += 1;
}
while target_lane < RECYCLED_HINT_LANES {
packed |= (INVALID_RECYCLED_HINT as u32) << (target_lane * 8);
target_lane += 1;
}
self.recycled_hints.store(packed, Ordering::Relaxed);
}
fn finish_small_allocation(&self, index: u32, class_size: usize) -> usize {
let class_index = self
.class_index()
.expect("a small allocation belongs to a size class");
self.base + small_payload_offset(class_index) + index as usize * class_size
}
pub unsafe fn deallocate_small(
&self,
address: usize,
layout: Layout,
current_owner: Option<u64>,
batch_remote: bool,
recent_free_word_hints: usize,
) -> Option<SmallDeallocation> {
let observed_owner = self.owner.load(Ordering::Acquire);
let observed_foreign = current_owner
.filter(|owner| *owner != 0)
.is_none_or(|current| current != observed_owner);
unsafe {
self.deallocate_small_published(
address,
layout,
batch_remote && observed_foreign,
(!observed_foreign).then_some(recent_free_word_hints),
)
}
}
unsafe fn deallocate_small_published(
&self,
address: usize,
layout: Layout,
queued: bool,
local_hint_words: Option<usize>,
) -> Option<SmallDeallocation> {
if self.kind() != SpanKind::Small {
return None;
}
let class_index = self.class_index()?;
let class_size = crate::config::SIZE_CLASSES[class_index];
let payload = self.base + small_payload_offset(class_index);
let offset = address.checked_sub(payload)?;
if offset % class_size != 0 || layout.size() > class_size {
return None;
}
let index = offset / class_size;
if index >= self.bump.load(Ordering::Acquire) as usize {
return None;
}
if queued {
unsafe { self.push_remote_free(address) };
}
if !queued {
let word = self.recycled.get(index / 64);
let mask = 1_u64 << (index % 64);
let previous = word.fetch_or(mask, Ordering::Release);
debug_assert_eq!(previous & mask, 0, "double free detected");
if let Some(hint_words) = local_hint_words {
self.record_recycled_word(index / 64, hint_words);
}
}
self.account_small_remote_deallocation(layout);
Some(SmallDeallocation)
}
unsafe fn push_remote_free(&self, address: usize) {
let mut head = self.remote_head.load(Ordering::Acquire);
loop {
unsafe { (address as *mut usize).write(head) };
match self.remote_head.compare_exchange(
head,
address,
Ordering::Release,
Ordering::Acquire,
) {
Ok(_) => return,
Err(actual) => head = actual,
}
}
}
fn drain_remote_frees(&self, recent_free_word_hints: usize) -> u32 {
let mut address = self.remote_head.swap(0, Ordering::AcqRel);
if address == 0 {
return 0;
}
let class_index = self
.class_index()
.expect("remote frees belong to a small span");
let class_size = crate::config::SIZE_CLASSES[class_index];
let payload = self.base + small_payload_offset(class_index);
let mut masks = [0_u64; MAX_BITMAP_WORDS];
let mut count = 0_u32;
while address != 0 {
let offset = address - payload;
let index = exact_block_index(offset, class_index);
debug_assert_eq!(offset % class_size, 0);
debug_assert!(index < self.bump.load(Ordering::Relaxed) as usize);
masks[index / 64] |= 1_u64 << (index % 64);
count += 1;
address = unsafe { (address as *const usize).read() };
}
for (word_index, mask) in masks[..self.recycled.len()].iter().copied().enumerate() {
if mask != 0 {
let previous = self
.recycled
.get(word_index)
.fetch_or(mask, Ordering::Release);
debug_assert_eq!(previous & mask, 0, "duplicate remote free detected");
self.record_recycled_word(word_index, recent_free_word_hints);
}
}
count
}
pub fn try_account_run_allocation(&self, requested: usize, usable: usize) -> bool {
let Some(_active) = self.try_enter() else {
return false;
};
if !matches!(self.kind(), SpanKind::Run | SpanKind::Dedicated)
|| self
.accounting
.compare_exchange(
0,
pack_accounting(1, requested),
Ordering::AcqRel,
Ordering::Acquire,
)
.is_err()
{
return false;
}
self.bump.store(1, Ordering::Release);
self.usable_live.store(usable, Ordering::Relaxed);
true
}
pub fn publish_empty_dedicated_commit_charge(&self, epoch: u64) -> bool {
let charged = DEDICATED_CHARGED_BIT
| (epoch & DEDICATED_CHARGE_EPOCH_MASK).max(DEDICATED_CHARGE_PENDING + 1);
self.last_touch
.compare_exchange(
DEDICATED_CHARGE_PENDING,
charged,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
}
pub fn take_empty_dedicated_commit_charge(&self) -> bool {
self.last_touch.swap(0, Ordering::AcqRel) & DEDICATED_CHARGED_BIT != 0
}
pub fn has_empty_dedicated_commit_charge(&self) -> bool {
self.empty_dedicated_commit_epoch().is_some()
}
pub fn empty_dedicated_commit_epoch(&self) -> Option<u64> {
let charge = self.last_touch.load(Ordering::Acquire);
(charge & DEDICATED_CHARGED_BIT != 0).then_some(charge & DEDICATED_CHARGE_EPOCH_MASK)
}
pub fn try_allocate_run_territory_batch<E>(
&self,
layout: Layout,
batch_capacity: u32,
mut commit: impl FnMut(usize, usize) -> Result<(), E>,
) -> Result<Option<RunTerritoryAllocation>, E> {
debug_assert_ne!(batch_capacity, 0);
let Some(_active) = self.try_enter() else {
return Ok(None);
};
if !self.is_run_territory() {
return Ok(None);
}
let extent_size = self
.run_extent_size()
.expect("a run territory has an extent stride");
let capacity = self.capacity();
let recycled = self.try_claim_run_recycled_index();
let (index, reserved_end, newly_committed) = if let Some(index) = recycled {
(index, index + 1, 0)
} else {
loop {
let index = self.bump.load(Ordering::Acquire);
if index >= capacity {
return Ok(None);
}
let reserved_end = index.saturating_add(batch_capacity).min(capacity);
let extent_base = self.base + index as usize * extent_size;
let commit_size = (reserved_end - index) as usize * extent_size;
commit(extent_base, commit_size)?;
match self.bump.compare_exchange_weak(
index,
reserved_end,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break (index, reserved_end, reserved_end - index),
Err(_) => std::hint::spin_loop(),
}
}
};
let extent_base = self.base + index as usize * extent_size;
let user = align_up_local(extent_base + size_of::<RunHeader>(), layout.align())
.expect("validated run alignment cannot overflow its reservation");
let usable = extent_base + extent_size - user;
debug_assert!(usable >= layout.size());
let previous = self
.accounting
.fetch_add(pack_accounting(1, layout.size()), Ordering::AcqRel);
debug_assert!(accounting_live(previous) < capacity);
self.usable_live.fetch_add(usable, Ordering::Relaxed);
Ok(Some(RunTerritoryAllocation {
user,
usable,
index,
reserved_end,
newly_committed,
}))
}
pub fn try_allocate_reserved_run_territory_index(
&self,
layout: Layout,
generation: u64,
index: u32,
) -> Option<(usize, usize)> {
let _active = self.try_enter()?;
if !self.is_run_territory()
|| self.generation.load(Ordering::Acquire) != generation
|| index >= self.bump.load(Ordering::Acquire)
{
return None;
}
let extent_size = self
.run_extent_size()
.expect("a run territory has an extent stride");
let extent_base = self.base + index as usize * extent_size;
let user = align_up_local(extent_base + size_of::<RunHeader>(), layout.align())
.expect("validated run alignment cannot overflow its reservation");
let usable = extent_base + extent_size - user;
debug_assert!(usable >= layout.size());
let previous = self
.accounting
.fetch_add(pack_accounting(1, layout.size()), Ordering::AcqRel);
debug_assert!(accounting_live(previous) < self.capacity());
self.usable_live.fetch_add(usable, Ordering::Relaxed);
Some((user, usable))
}
pub fn release_run_territory_reservation(&self, generation: u64, start: u32, end: u32) -> u32 {
if start >= end {
return 0;
}
if !self.is_run_territory()
|| self.generation.load(Ordering::Acquire) != generation
|| end > self.bump.load(Ordering::Acquire)
{
return 0;
}
debug_assert!(end <= 64, "run territories use one recycled word");
let upper = if end == 64 {
u64::MAX
} else {
(1_u64 << end) - 1
};
let lower = if start == 0 { 0 } else { (1_u64 << start) - 1 };
let mask = upper & !lower;
let previous = self.recycled.get(0).fetch_or(mask, Ordering::Release);
debug_assert_eq!(previous & mask, 0, "reserved run slot published twice");
end - start
}
fn try_claim_run_recycled_index(&self) -> Option<u32> {
debug_assert!(self.is_run_territory());
debug_assert_eq!(self.recycled.len(), 1);
let word = self.recycled.get(0);
let mut current = word.load(Ordering::Acquire);
while current != 0 {
let index = current.trailing_zeros();
if index >= self.capacity() {
return None;
}
let mask = 1_u64 << index;
match word.compare_exchange_weak(
current,
current & !mask,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return Some(index),
Err(actual) => current = actual,
}
}
None
}
pub fn record_foreign_miss(&self) -> u64 {
let touch = self.last_touch.load(Ordering::Acquire);
let misses = if self.foreign_touch.swap(touch, Ordering::AcqRel) != touch {
self.foreign_misses.store(1, Ordering::Relaxed);
1
} else {
self.foreign_misses
.fetch_update(Ordering::Relaxed, Ordering::Relaxed, |current| {
Some(current.saturating_add(1))
})
.unwrap_or(u64::MAX)
.saturating_add(1)
};
self.control
.fetch_or(CONTROL_FOREIGN_PROBED, Ordering::Release);
misses
}
pub fn cohort_epoch(&self) -> u64 {
if self.kind() != SpanKind::Small {
return 0;
}
self.last_touch.load(Ordering::Acquire) & COHORT_EPOCH_MASK
}
pub fn is_cohort_sealed(&self) -> bool {
self.kind() == SpanKind::Small
&& self.last_touch.load(Ordering::Acquire) & COHORT_SEALED_BIT != 0
}
pub fn begin_small_cohort(&self, owner: u64, generation: u64, epoch: u64) -> bool {
if epoch == 0
|| self.kind() != SpanKind::Small
|| self.owner.load(Ordering::Acquire) != owner
|| self.generation.load(Ordering::Acquire) != generation
|| self.is_cohort_sealed()
{
return false;
}
self.last_touch
.store(epoch & COHORT_EPOCH_MASK, Ordering::Release);
true
}
pub fn seal_small_cohort(&self, owner: u64, generation: u64) -> bool {
if self.kind() != SpanKind::Small
|| self.owner.load(Ordering::Acquire) != owner
|| self.generation.load(Ordering::Acquire) != generation
{
return false;
}
let mut cohort = self.last_touch.load(Ordering::Acquire);
loop {
if cohort & COHORT_EPOCH_MASK == 0 || cohort & COHORT_SEALED_BIT != 0 {
return false;
}
match self.last_touch.compare_exchange_weak(
cohort,
cohort | COHORT_SEALED_BIT,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return true,
Err(actual) => cohort = actual,
}
}
}
pub fn try_recycle_empty_cohort(&self, expected_owner: u64) -> bool {
if self.kind() != SpanKind::Small
|| self.cohort_epoch() == 0
|| self.owner.load(Ordering::Acquire) != expected_owner
|| !self.try_freeze_empty()
{
return false;
}
if self.kind() != SpanKind::Small
|| self.owner.load(Ordering::Acquire) != expected_owner
|| self.live() != 0
{
self.unfreeze();
return false;
}
self.last_touch.store(0, Ordering::Relaxed);
self.generation.fetch_add(1, Ordering::AcqRel);
self.owner.store(0, Ordering::Release);
self.unfreeze();
true
}
pub fn try_transfer_empty_small(
&self,
class_index: usize,
expected_owner: u64,
new_owner: u64,
) -> bool {
if expected_owner == 0
|| expected_owner == new_owner
|| self.kind() != SpanKind::Small
|| self.class_index() != Some(class_index)
|| self.owner.load(Ordering::Acquire) != expected_owner
|| self.live() != 0
|| !self.try_freeze_empty()
{
return false;
}
if self.kind() != SpanKind::Small
|| self.class_index() != Some(class_index)
|| self.owner.load(Ordering::Acquire) != expected_owner
|| self.live() != 0
{
self.unfreeze();
return false;
}
if self
.owner
.compare_exchange(
expected_owner,
new_owner,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_err()
{
self.unfreeze();
return false;
}
self.last_touch.store(0, Ordering::Relaxed);
self.generation.fetch_add(1, Ordering::AcqRel);
self.unfreeze();
true
}
pub(crate) fn foreign_misses(&self) -> u64 {
self.foreign_misses.load(Ordering::Relaxed)
}
pub fn deallocate_run(&self, address: usize, layout: Layout) -> bool {
let Some(_active) = self.try_enter_deallocate() else {
return false;
};
if !matches!(self.kind(), SpanKind::Run | SpanKind::Dedicated) {
return false;
}
if self.is_run_territory() {
let extent_size = self
.run_extent_size()
.expect("a run territory has an extent stride");
let index = (address - self.base) / extent_size;
if index >= self.bump.load(Ordering::Acquire) as usize {
return false;
}
let extent_base = self.base + index * extent_size;
let expected = align_up_local(extent_base + size_of::<RunHeader>(), layout.align())
.expect("a live run address remains representable");
debug_assert_eq!(address, expected);
if address != expected {
return false;
}
let usable = extent_base + extent_size - address;
let delta = pack_accounting(1, layout.size());
let previous = self.accounting.fetch_sub(delta, Ordering::AcqRel);
debug_assert_ne!(accounting_live(previous), 0);
debug_assert!(accounting_requested(previous) >= layout.size());
let previous_usable = self.usable_live.fetch_sub(usable, Ordering::Relaxed);
debug_assert!(previous_usable >= usable);
let mask = 1_u64 << index;
let previous = self.recycled.get(0).fetch_or(mask, Ordering::Release);
debug_assert_eq!(previous & mask, 0, "run territory slot freed twice");
return true;
}
if self.kind() == SpanKind::Dedicated {
self.last_touch
.store(DEDICATED_CHARGE_PENDING, Ordering::Relaxed);
}
let accounting = self.accounting.swap(0, Ordering::AcqRel);
if accounting_live(accounting) != 1 {
if self.kind() == SpanKind::Dedicated {
self.last_touch.store(0, Ordering::Relaxed);
}
return false;
}
debug_assert_eq!(accounting_requested(accounting), layout.size());
self.usable_live.store(0, Ordering::Relaxed);
true
}
pub fn committed_bytes(&self) -> usize {
match self.kind() {
SpanKind::Small | SpanKind::Dedicated | SpanKind::DedicatedReserved => self.size,
SpanKind::Run if self.is_run_territory() => {
self.run_high_water() as usize
* self
.run_extent_size()
.expect("a run territory has an extent stride")
}
SpanKind::Run => usize::from(self.run_high_water() != 0) * self.size,
SpanKind::Free
| SpanKind::ReservedSmall
| SpanKind::ReservedRun
| SpanKind::Retired => 0,
}
}
pub fn try_freeze_empty(&self) -> bool {
if !self.transition_control_state(STATE_ACTIVE, STATE_FREEZING) {
return false;
}
for _ in 0..128 {
if active_operations(self.control.load(Ordering::Acquire)) == 0 {
break;
}
std::hint::spin_loop();
}
let control = self.control.load(Ordering::Acquire);
if control_state(control) != STATE_FREEZING
|| active_operations(control) != 0
|| self.live() != 0
{
let _ = self.transition_control_state(STATE_FREEZING, STATE_ACTIVE);
return false;
}
let frozen = (control & !CONTROL_STATE_MASK) | STATE_FROZEN as u32;
match self
.control
.compare_exchange(control, frozen, Ordering::AcqRel, Ordering::Acquire)
{
Ok(_) => true,
Err(_) => {
let _ = self.transition_control_state(STATE_FREEZING, STATE_ACTIVE);
false
}
}
}
pub fn try_freeze_reserved(&self, class_index: usize, owner: u64) -> bool {
if self.kind() != SpanKind::ReservedSmall
|| self.class_index() != Some(class_index)
|| self.owner.load(Ordering::Acquire) != owner
|| !self.try_freeze_empty()
{
return false;
}
if self.kind() == SpanKind::ReservedSmall
&& self.class_index() == Some(class_index)
&& self.owner.load(Ordering::Acquire) == owner
{
true
} else {
self.unfreeze();
false
}
}
pub fn try_freeze_reserved_run(&self, owner: u64) -> bool {
if self.kind() != SpanKind::ReservedRun
|| self.owner.load(Ordering::Acquire) != owner
|| !self.try_freeze_empty()
{
return false;
}
if self.kind() == SpanKind::ReservedRun && self.owner.load(Ordering::Acquire) == owner {
true
} else {
self.unfreeze();
false
}
}
pub fn try_freeze_reserved_dedicated(&self) -> bool {
if self.kind() != SpanKind::DedicatedReserved || !self.try_freeze_empty() {
return false;
}
if self.kind() == SpanKind::DedicatedReserved {
true
} else {
self.unfreeze();
false
}
}
pub fn finish_dedicated_discard(&self) {
debug_assert_eq!(self.kind(), SpanKind::Dedicated);
debug_assert_eq!(self.live(), 0);
debug_assert!(self.has_empty_dedicated_commit_charge());
self.last_touch.store(0, Ordering::Relaxed);
self.generation.fetch_add(1, Ordering::AcqRel);
self.kind
.store(SpanKind::DedicatedReserved as u8, Ordering::Release);
assert!(self.transition_control_state(STATE_FROZEN, STATE_ACTIVE));
}
pub fn advance_reserved_generation(&self) -> u64 {
debug_assert_eq!(self.kind(), SpanKind::ReservedSmall);
self.generation.fetch_add(1, Ordering::AcqRel) + 1
}
pub fn advance_reserved_run_generation(&self) -> u64 {
debug_assert_eq!(self.kind(), SpanKind::ReservedRun);
self.generation.fetch_add(1, Ordering::AcqRel) + 1
}
pub fn activate_reserved_with_first_allocation(&self, layout: Layout) -> usize {
debug_assert_eq!(self.kind(), SpanKind::ReservedSmall);
debug_assert_eq!(self.live(), 0);
debug_assert!(self.capacity() != 0);
self.bump.store(1, Ordering::Relaxed);
self.usable_live.store(0, Ordering::Relaxed);
self.accounting
.store(pack_accounting(1, layout.size()), Ordering::Relaxed);
self.kind.store(SpanKind::Small as u8, Ordering::Release);
assert!(self.transition_control_state(STATE_FROZEN, STATE_ACTIVE));
let class_index = self
.class_index()
.expect("a reserved small span belongs to a size class");
self.base + small_payload_offset(class_index)
}
pub fn activate_reserved_run_with_first_allocation(&self, requested: usize, usable: usize) {
debug_assert_eq!(self.kind(), SpanKind::ReservedRun);
debug_assert_eq!(self.live(), 0);
self.bump.store(1, Ordering::Relaxed);
self.accounting
.store(pack_accounting(1, requested), Ordering::Relaxed);
self.usable_live.store(usable, Ordering::Relaxed);
self.kind.store(SpanKind::Run as u8, Ordering::Release);
assert!(self.transition_control_state(STATE_FROZEN, STATE_ACTIVE));
}
pub fn activate_reserved_dedicated_with_first_allocation(
&self,
requested: usize,
usable: usize,
) {
debug_assert_eq!(self.kind(), SpanKind::DedicatedReserved);
debug_assert_eq!(self.live(), 0);
self.bump.store(1, Ordering::Relaxed);
self.accounting
.store(pack_accounting(1, requested), Ordering::Relaxed);
self.usable_live.store(usable, Ordering::Relaxed);
self.generation.fetch_add(1, Ordering::AcqRel);
self.kind
.store(SpanKind::Dedicated as u8, Ordering::Release);
assert!(self.transition_control_state(STATE_FROZEN, STATE_ACTIVE));
}
pub fn unfreeze(&self) {
assert!(self.transition_control_state(STATE_FROZEN, STATE_ACTIVE));
}
pub fn retire(&self) {
self.kind.store(SpanKind::Retired as u8, Ordering::Release);
self.generation.fetch_add(1, Ordering::AcqRel);
let mut control = self.control.load(Ordering::Acquire);
loop {
if active_operations(control) != 0 {
std::hint::spin_loop();
control = self.control.load(Ordering::Acquire);
continue;
}
if control_state(control) == STATE_RETIRED {
return;
}
match self.control.compare_exchange_weak(
control,
STATE_RETIRED as u32,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return,
Err(actual) => control = actual,
}
}
}
}
fn control_state(control: u32) -> u8 {
(control & CONTROL_STATE_MASK) as u8
}
fn active_operations(control: u32) -> u32 {
control / CONTROL_ACTIVE_ONE
}
fn align_up_local(value: usize, align: usize) -> Option<usize> {
value
.checked_add(align - 1)
.map(|value| value & !(align - 1))
}
fn pack_accounting(live: u32, requested: usize) -> u64 {
debug_assert!(live as u64 <= ACCOUNT_LIVE_MASK);
debug_assert!(requested <= (u64::MAX >> ACCOUNT_LIVE_BITS) as usize);
(requested as u64) << ACCOUNT_LIVE_BITS | live as u64
}
fn accounting_live(accounting: u64) -> u32 {
(accounting & ACCOUNT_LIVE_MASK) as u32
}
fn accounting_requested(accounting: u64) -> usize {
(accounting >> ACCOUNT_LIVE_BITS) as usize
}
fn subtract_accounting(owned: u64, remote: u64) -> u64 {
let owned_live = accounting_live(owned);
let remote_live = accounting_live(remote);
let owned_requested = accounting_requested(owned);
let remote_requested = accounting_requested(remote);
if owned_live < remote_live || owned_requested < remote_requested {
return owned;
}
pack_accounting(owned_live - remote_live, owned_requested - remote_requested)
}
fn saturating_subtract_accounting(owned: u64, remote: u64) -> u64 {
pack_accounting(
accounting_live(owned).saturating_sub(accounting_live(remote)),
accounting_requested(owned).saturating_sub(accounting_requested(remote)),
)
}
struct ActiveOp<'a>(&'a SpanDesc);
impl Drop for ActiveOp<'_> {
fn drop(&mut self) {
let previous = self
.0
.control
.fetch_sub(CONTROL_ACTIVE_ONE, Ordering::Release);
debug_assert_ne!(active_operations(previous), 0);
}
}
#[cfg(test)]
mod tests {
use super::{
BITMAP_ALIGNMENT, BitmapSlab, INVALID_RECYCLED_HINT, SPAN_SLOT_BYTES, SpanDesc, SpanHandle,
SpanSlabOwner, exact_block_index, small_payload_offset,
};
use crate::config::{SIZE_CLASSES, SMALL_PAYLOAD_OFFSET, small_span_capacity};
use std::alloc::Layout;
use std::sync::Arc;
use std::sync::atomic::Ordering;
use std::thread;
#[test]
fn reciprocal_block_index_matches_exact_division_for_every_small_slot() {
for (class_index, class_size) in SIZE_CLASSES.iter().copied().enumerate() {
let capacity = small_span_capacity(class_index);
for index in 0..capacity {
let offset = index * class_size;
assert_eq!(exact_block_index(offset, class_index), index);
}
}
}
#[test]
fn recycled_bitmaps_are_cache_line_aligned() {
let slab = BitmapSlab::new();
for len in [1, 2, 10, 120] {
let bitmap = slab.allocate(len);
assert_eq!(bitmap.pointer.as_ptr() as usize % BITMAP_ALIGNMENT, 0);
}
}
#[test]
fn recent_free_word_hints_compact_consumed_words() {
const CLASS_INDEX: usize = 6;
const CLASS_SIZE: usize = 96;
let slab = SpanSlabOwner::new();
let span = slab.allocate(SpanDesc::small(
0x10_0000,
0x10_0000,
CLASS_INDEX,
CLASS_SIZE,
));
span.bump.store(span.capacity(), Ordering::Relaxed);
for word_index in [1_usize, 3, 5, 8] {
span.recycled
.get(word_index)
.store(1_u64 << 2, Ordering::Relaxed);
span.record_recycled_word(word_index, 4);
}
assert_eq!(span.recycled_hints.load(Ordering::Relaxed), 0x01_03_05_08);
let first = span
.try_claim_recycled_hints(CLASS_SIZE, 4)
.expect("newest hinted word must contain a free block");
assert_eq!(
first,
span.base + SMALL_PAYLOAD_OFFSET + (8 * 64 + 2) * CLASS_SIZE
);
assert_eq!(span.recycled_hints.load(Ordering::Relaxed), 0xff_01_03_05);
let second = span
.try_claim_recycled_hints(CLASS_SIZE, 1)
.expect("a shallow probe must consume the next compacted hint");
assert_eq!(
second,
span.base + SMALL_PAYLOAD_OFFSET + (5 * 64 + 2) * CLASS_SIZE
);
let packed = span.recycled_hints.load(Ordering::Relaxed);
assert_eq!(packed as u8, 3);
assert_eq!(((packed >> 8) & 0xff) as u8, INVALID_RECYCLED_HINT);
assert_eq!(((packed >> 16) & 0xff) as u8, INVALID_RECYCLED_HINT);
span.recycled_hints.store(u32::MAX, Ordering::Relaxed);
for word_index in [1_usize, 3, 5, 8] {
span.record_recycled_word(word_index, 1);
}
assert_eq!(span.recycled_hints.load(Ordering::Relaxed), 0xff_ff_ff_08);
}
#[test]
fn allocation_entry_resets_only_an_observed_foreign_miss_sequence() {
let span = SpanDesc::reserved_small(0x10_0000, 0x10_0000, 5, 64);
drop(span.try_enter().unwrap());
assert_eq!(span.last_touch.load(Ordering::Relaxed), 0);
assert_eq!(span.record_foreign_miss(), 1);
assert_eq!(span.record_foreign_miss(), 2);
drop(span.try_enter().unwrap());
assert_eq!(span.last_touch.load(Ordering::Relaxed), 1);
assert_eq!(span.foreign_misses(), 0);
assert_eq!(span.record_foreign_miss(), 1);
}
#[test]
fn sealed_cohort_rejects_allocation_and_recycles_only_when_empty() {
const CLASS_INDEX: usize = 6;
let slab = SpanSlabOwner::new();
let span = slab.allocate(SpanDesc::small(
0x10_0000,
0x10_0000,
CLASS_INDEX,
SIZE_CLASSES[CLASS_INDEX],
));
span.owner.store(7, Ordering::Release);
let generation = span.generation.load(Ordering::Acquire);
assert!(span.begin_small_cohort(7, generation, 11));
let layout = Layout::from_size_align(96, 32).unwrap();
let (address, _) = span
.try_allocate_small(CLASS_INDEX, layout, 7, generation, 4)
.unwrap();
assert!(span.seal_small_cohort(7, generation));
assert!(span.is_cohort_sealed());
assert!(!span.has_capacity());
assert!(!span.try_recycle_empty_cohort(7));
assert!(unsafe { span.deallocate_small(address, layout, Some(7), false, 4) }.is_some());
assert_eq!(span.live(), 0);
assert!(span.try_recycle_empty_cohort(7));
assert_eq!(span.owner.load(Ordering::Acquire), 0);
assert_eq!(span.cohort_epoch(), 0);
assert!(!span.is_cohort_sealed());
assert!(span.generation.load(Ordering::Acquire) > generation);
}
#[test]
fn split_accounting_stays_exact_until_owner_synchronizes_remote_frees() {
let span = SpanDesc::small(0x10_0000, 0x10_0000, 6, 96);
let full = Layout::from_size_align(96, 8).unwrap();
let short = Layout::from_size_align(80, 8).unwrap();
span.account_small_allocation(full);
span.account_small_allocation(short);
assert_eq!(span.live(), 2);
assert_eq!(span.requested_live(), 176);
span.account_small_remote_deallocation(full);
assert_eq!(span.live(), 1);
assert_eq!(span.requested_live(), 80);
span.account_small_owner_deallocation(short);
assert_eq!(span.live(), 0);
assert_eq!(span.requested_live(), 0);
assert_ne!(span.usable_live.load(Ordering::Relaxed), 0);
span.synchronize_remote_accounting();
assert_eq!(span.live(), 0);
assert_eq!(span.requested_live(), 0);
assert_eq!(span.usable_live.load(Ordering::Relaxed), 0);
}
#[test]
fn cached_remote_batch_publishes_unique_words_and_exact_requested_bytes() {
const CLASS_INDEX: usize = 6;
let slab = SpanSlabOwner::new();
let span = slab.allocate(SpanDesc::small(
0x20_0000,
0x20_0000,
CLASS_INDEX,
SIZE_CLASSES[CLASS_INDEX],
));
span.owner.store(7, Ordering::Release);
let generation = span.generation.load(Ordering::Acquire);
let full = Layout::from_size_align(96, 32).unwrap();
let short = Layout::from_size_align(80, 16).unwrap();
let first = span
.try_allocate_small(CLASS_INDEX, full, 7, generation, 4)
.unwrap()
.0;
let second = span
.try_allocate_small(CLASS_INDEX, short, 7, generation, 4)
.unwrap()
.0;
assert_eq!(span.requested_live(), 176);
unsafe {
span.publish_remote_cached_batch(&[first, second], &[96, 80], CLASS_INDEX);
}
assert_eq!(span.live(), 0);
assert_eq!(span.requested_live(), 0);
let payload = span.base + small_payload_offset(CLASS_INDEX);
for address in [first, second] {
let index = exact_block_index(address - payload, CLASS_INDEX);
assert_ne!(
span.recycled.get(index / 64).load(Ordering::Acquire) & (1_u64 << (index % 64)),
0
);
}
}
#[test]
fn packed_control_reopens_after_busy_freeze_and_excludes_when_frozen() {
let span = SpanDesc::small(0x10_0000, 0x10_0000, 5, 64);
let active = span
.try_enter()
.expect("active span must admit an operation");
assert!(!span.try_freeze_empty());
drop(active);
assert!(span.try_freeze_empty());
assert!(span.try_enter().is_none());
span.unfreeze();
assert!(span.try_enter().is_some());
}
#[test]
fn bitmap_slab_reuses_and_reinitializes_same_class_slots() {
let slab = BitmapSlab::new();
let first = slab.allocate(10);
let address = first.pointer.as_ptr() as usize;
for word in first.iter() {
word.store(u64::MAX, std::sync::atomic::Ordering::Relaxed);
}
drop(first);
let reused = slab.allocate(9);
assert_eq!(reused.pointer.as_ptr() as usize, address);
assert!(
reused
.iter()
.all(|word| word.load(std::sync::atomic::Ordering::Relaxed) == 0)
);
assert_eq!(slab.allocated_blocks(), 1);
assert_eq!(slab.reused(), 1);
}
#[test]
fn concurrent_bitmap_slab_reuse_keeps_each_live_slot_exclusive() {
const THREADS: usize = 8;
const ITERATIONS: usize = 10_000;
let slab = Arc::new(BitmapSlab::new());
let mut workers = Vec::new();
for thread_index in 0..THREADS {
let slab = Arc::clone(&slab);
workers.push(thread::spawn(move || {
for iteration in 0..ITERATIONS {
let bitmap = slab.allocate(10);
let marker = ((thread_index + 1) as u64) << 32 | iteration as u64;
assert_eq!(bitmap.get(0).swap(marker, Ordering::AcqRel), 0);
assert_eq!(bitmap.get(0).load(Ordering::Acquire), marker);
}
}));
}
for worker in workers {
worker.join().unwrap();
}
assert_eq!(slab.live(), 0);
assert!(slab.slots() <= 64, "unexpected bitmap slot growth");
assert!(slab.reused() >= (THREADS * ITERATIONS - 64) as u64);
}
#[test]
fn span_slab_reuses_only_after_the_last_handle_drops() {
let slab = SpanSlabOwner::new();
let first = slab.allocate(SpanDesc::free(0x10_0000, 4096, 0x10_0000));
let first_address = first.as_ptr() as usize;
assert_eq!(first_address % 64, 0);
assert_eq!(slab.allocated_blocks(), 1);
assert_eq!(slab.slots(), 1);
assert_eq!(slab.live(), 1);
let retained = first.clone();
drop(first);
let second = slab.allocate(SpanDesc::free(0x20_0000, 4096, 0x20_0000));
assert_ne!(second.as_ptr() as usize, first_address);
assert_eq!(slab.slots(), 2);
assert_eq!(slab.live(), 2);
assert_eq!(slab.reused(), 0);
drop(retained);
let reused = slab.allocate(SpanDesc::free(0x30_0000, 4096, 0x30_0000));
assert_eq!(reused.as_ptr() as usize, first_address);
assert_eq!(reused.base, 0x30_0000);
assert_eq!(slab.slots(), 2);
assert_eq!(slab.live(), 2);
assert_eq!(slab.reused(), 1);
assert!(!SpanHandle::ptr_eq(&second, &reused));
assert_eq!(
(second.as_ptr() as usize).abs_diff(reused.as_ptr() as usize),
SPAN_SLOT_BYTES
);
}
#[test]
fn span_slab_attaches_and_reuses_size_class_bitmap_storage() {
let slab = SpanSlabOwner::new();
let first = slab.allocate(SpanDesc::small(0x10_0000, 0x10_0000, 6, 96));
let bitmap_address = first.recycled.pointer.as_ptr() as usize;
assert_eq!(slab.allocated_blocks(), 2);
assert_eq!(slab.bitmap_slots(), 1);
assert_eq!(slab.live_bitmaps(), 1);
drop(first);
assert_eq!(slab.live_bitmaps(), 0);
let second = slab.allocate(SpanDesc::small(0x20_0000, 0x20_0000, 6, 96));
assert_eq!(second.recycled.pointer.as_ptr() as usize, bitmap_address);
assert_eq!(slab.bitmap_slots(), 1);
assert_eq!(slab.live_bitmaps(), 1);
assert_eq!(slab.reused_bitmaps(), 1);
}
#[test]
fn span_handle_keeps_the_slab_alive_after_owner_drop() {
let descriptor = {
let slab = SpanSlabOwner::new();
let descriptor = slab.allocate(SpanDesc::free(0x40_0000, 8192, 0x40_0000));
assert_eq!(slab.live(), 1);
descriptor
};
assert_eq!(descriptor.base, 0x40_0000);
assert_eq!(descriptor.size, 8192);
let clone = descriptor.clone();
drop(descriptor);
assert_eq!(clone.chunk_base, 0x40_0000);
drop(clone);
}
}