use std::fmt;
use std::iter::FromIterator;
use std::marker::PhantomData;
use std::mem::{align_of, size_of};
use std::ops::{Deref, DerefMut};
use std::ptr::NonNull;
use std::sync::atomic::{fence, AtomicU64, AtomicUsize, Ordering};
use crate::os::{release_metadata_block, reserve_commit_metadata_block};
const METADATA_BLOCK_BYTES: usize = 64 * 1024;
const MAX_BLOCKS: usize = 4096;
const FREE_INDEX_BITS: u32 = 21;
const FREE_INDEX_MASK: u64 = (1_u64 << FREE_INDEX_BITS) - 1;
#[repr(C, align(64))]
struct SlotHeader {
next_free: AtomicUsize,
_padding: [usize; 7],
}
const _: () = assert!(size_of::<SlotHeader>() == 64);
struct RawVecSlab<T, const CAPACITY: usize, const SLOT_BYTES: usize> {
blocks: [AtomicUsize; MAX_BLOCKS],
lifetime_references: AtomicUsize,
next: AtomicUsize,
free_head: AtomicU64,
live: AtomicUsize,
reused: AtomicU64,
_marker: PhantomData<T>,
}
unsafe impl<T: Send, const CAPACITY: usize, const SLOT_BYTES: usize> Send
for RawVecSlab<T, CAPACITY, SLOT_BYTES>
{
}
unsafe impl<T: Sync, const CAPACITY: usize, const SLOT_BYTES: usize> Sync
for RawVecSlab<T, CAPACITY, SLOT_BYTES>
{
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> RawVecSlab<T, CAPACITY, SLOT_BYTES> {
fn new() -> Self {
assert!(SLOT_BYTES % 64 == 0);
assert!(SLOT_BYTES >= size_of::<SlotHeader>() + CAPACITY * size_of::<T>());
assert!(align_of::<T>() <= 64);
Self {
blocks: std::array::from_fn(|_| AtomicUsize::new(0)),
lifetime_references: AtomicUsize::new(1),
next: AtomicUsize::new(0),
free_head: AtomicU64::new(0),
live: AtomicUsize::new(0),
reused: AtomicU64::new(0),
_marker: PhantomData,
}
}
fn slots_per_block() -> usize {
METADATA_BLOCK_BYTES / SLOT_BYTES
}
fn block(&self, block_index: usize) -> usize {
assert!(
block_index < MAX_BLOCKS,
"immutable payload vector slab exhausted"
);
let current = self.blocks[block_index].load(Ordering::Acquire);
if current != 0 {
return current;
}
let candidate = unsafe { reserve_commit_metadata_block(METADATA_BLOCK_BYTES) }
.unwrap_or_else(|error| panic!("unable to reserve payload metadata block: {error}"));
for offset in 0..Self::slots_per_block() {
let header = (candidate + offset * SLOT_BYTES) as *mut SlotHeader;
unsafe {
header.write(SlotHeader {
next_free: AtomicUsize::new(0),
_padding: [0; 7],
})
};
}
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 header(&self, index: usize) -> &SlotHeader {
let slots_per_block = Self::slots_per_block();
let block = self.block(index / slots_per_block);
unsafe { &*((block + (index % slots_per_block) * SLOT_BYTES) as *const SlotHeader) }
}
fn pointer(&self, index: usize) -> NonNull<T> {
let header = self.header(index) as *const SlotHeader as usize;
unsafe { NonNull::new_unchecked((header + size_of::<SlotHeader>()) as *mut T) }
}
fn pop_free(&self) -> Option<usize> {
let mut head = self.free_head.load(Ordering::Acquire);
loop {
let encoded = (head & FREE_INDEX_MASK) as usize;
if encoded == 0 {
return None;
}
let index = encoded - 1;
let next = self.header(index).next_free.load(Ordering::Acquire);
let tag = (head >> FREE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << 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("payload vector index overflow");
assert!(encoded <= FREE_INDEX_MASK as usize);
let header = self.header(index);
let mut head = self.free_head.load(Ordering::Acquire);
loop {
header
.next_free
.store((head & FREE_INDEX_MASK) as usize, Ordering::Release);
let tag = (head >> FREE_INDEX_BITS).wrapping_add(1);
let replacement = (tag << 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, values: Vec<T>) -> FrozenVec<T, CAPACITY, SLOT_BYTES> {
assert!(
values.len() <= CAPACITY,
"immutable payload exceeds B-Link fanout"
);
let len = values.len();
let reused = self.pop_free();
let index = reused.unwrap_or_else(|| self.next.fetch_add(1, Ordering::AcqRel));
let pointer = self.pointer(index);
for (offset, value) in values.into_iter().enumerate() {
unsafe { pointer.as_ptr().add(offset).write(value) };
}
let lifetime = self.lifetime_references.fetch_add(1, Ordering::Relaxed);
assert!(lifetime != 0 && lifetime < usize::MAX / 2);
self.live.fetch_add(1, Ordering::Relaxed);
if reused.is_some() {
self.reused.fetch_add(1, Ordering::Relaxed);
}
FrozenVec {
pointer,
len,
index,
slab: NonNull::from(self),
}
}
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()
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> Drop
for RawVecSlab<T, CAPACITY, SLOT_BYTES>
{
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 PayloadVecSlabOwner<T, const CAPACITY: usize, const SLOT_BYTES: usize> {
slab: NonNull<RawVecSlab<T, CAPACITY, SLOT_BYTES>>,
}
unsafe impl<T: Send, const CAPACITY: usize, const SLOT_BYTES: usize> Send
for PayloadVecSlabOwner<T, CAPACITY, SLOT_BYTES>
{
}
unsafe impl<T: Sync, const CAPACITY: usize, const SLOT_BYTES: usize> Sync
for PayloadVecSlabOwner<T, CAPACITY, SLOT_BYTES>
{
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize>
PayloadVecSlabOwner<T, CAPACITY, SLOT_BYTES>
{
pub fn new() -> Self {
let slab = Box::new(RawVecSlab::new());
Self {
slab: unsafe { NonNull::new_unchecked(Box::into_raw(slab)) },
}
}
pub fn freeze(&self, values: Vec<T>) -> PayloadVec<T, CAPACITY, SLOT_BYTES> {
if values.is_empty() {
return PayloadVec::Empty;
}
PayloadVec::Frozen(unsafe { self.slab.as_ref() }.allocate(values))
}
pub fn slots(&self) -> usize {
unsafe { self.slab.as_ref() }.next.load(Ordering::Relaxed)
}
pub fn live(&self) -> usize {
unsafe { self.slab.as_ref() }.live.load(Ordering::Relaxed)
}
pub fn reused(&self) -> u64 {
unsafe { self.slab.as_ref() }.reused.load(Ordering::Relaxed)
}
pub fn allocated_blocks(&self) -> usize {
unsafe { self.slab.as_ref() }.allocated_blocks()
}
pub fn control_bytes(&self) -> usize {
size_of::<RawVecSlab<T, CAPACITY, SLOT_BYTES>>()
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> Drop
for PayloadVecSlabOwner<T, CAPACITY, SLOT_BYTES>
{
fn drop(&mut self) {
unsafe { RawVecSlab::release_lifetime(self.slab) };
}
}
pub(crate) struct FrozenVec<T, const CAPACITY: usize, const SLOT_BYTES: usize> {
pointer: NonNull<T>,
len: usize,
index: usize,
slab: NonNull<RawVecSlab<T, CAPACITY, SLOT_BYTES>>,
}
unsafe impl<T: Send, const CAPACITY: usize, const SLOT_BYTES: usize> Send
for FrozenVec<T, CAPACITY, SLOT_BYTES>
{
}
unsafe impl<T: Sync, const CAPACITY: usize, const SLOT_BYTES: usize> Sync
for FrozenVec<T, CAPACITY, SLOT_BYTES>
{
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> FrozenVec<T, CAPACITY, SLOT_BYTES> {
fn as_slice(&self) -> &[T] {
unsafe { std::slice::from_raw_parts(self.pointer.as_ptr(), self.len) }
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> Drop
for FrozenVec<T, CAPACITY, SLOT_BYTES>
{
fn drop(&mut self) {
unsafe {
std::ptr::drop_in_place(std::ptr::slice_from_raw_parts_mut(
self.pointer.as_ptr(),
self.len,
))
};
let slab = unsafe { self.slab.as_ref() };
slab.live.fetch_sub(1, Ordering::Relaxed);
slab.push_free(self.index);
unsafe { RawVecSlab::release_lifetime(self.slab) };
}
}
pub(crate) enum PayloadVec<T, const CAPACITY: usize, const SLOT_BYTES: usize> {
Mutable(Vec<T>),
Empty,
Frozen(FrozenVec<T, CAPACITY, SLOT_BYTES>),
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> PayloadVec<T, CAPACITY, SLOT_BYTES> {
pub fn freeze(self, owner: &PayloadVecSlabOwner<T, CAPACITY, SLOT_BYTES>) -> Self {
match self {
Self::Mutable(values) => owner.freeze(values),
frozen @ (Self::Empty | Self::Frozen(_)) => frozen,
}
}
fn mutable(&mut self) -> &mut Vec<T> {
match self {
Self::Mutable(values) => values,
Self::Empty | Self::Frozen(_) => {
panic!("attempted to mutate an immutable B-Link payload")
}
}
}
pub fn capacity(&self) -> usize {
match self {
Self::Mutable(values) => values.capacity(),
Self::Empty => 0,
Self::Frozen(_) => self.len(),
}
}
pub fn is_frozen(&self) -> bool {
matches!(self, Self::Empty | Self::Frozen(_))
}
pub fn insert(&mut self, index: usize, value: T) {
self.mutable().insert(index, value);
}
pub fn remove(&mut self, index: usize) -> T {
self.mutable().remove(index)
}
pub fn push(&mut self, value: T) {
self.mutable().push(value);
}
pub fn pop(&mut self) -> Option<T> {
self.mutable().pop()
}
pub fn split_off(&mut self, at: usize) -> Self {
Self::Mutable(self.mutable().split_off(at))
}
pub fn extend<I: IntoIterator<Item = T>>(&mut self, values: I) {
self.mutable().extend(values);
}
pub fn into_boxed_slice(self) -> Box<[T]> {
match self {
Self::Mutable(values) => values.into_boxed_slice(),
Self::Empty => Vec::new().into_boxed_slice(),
Self::Frozen(values) => {
let mut values = std::mem::ManuallyDrop::new(values);
let moved = (0..values.len)
.map(|index| unsafe { values.pointer.as_ptr().add(index).read() })
.collect::<Vec<_>>()
.into_boxed_slice();
values.len = 0;
unsafe { std::mem::ManuallyDrop::drop(&mut values) };
moved
}
}
}
}
impl<T: Clone, const CAPACITY: usize, const SLOT_BYTES: usize> Clone
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
fn clone(&self) -> Self {
Self::Mutable(self.iter().cloned().collect())
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> Default
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
fn default() -> Self {
Self::Mutable(Vec::new())
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> From<Vec<T>>
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
fn from(values: Vec<T>) -> Self {
Self::Mutable(values)
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> FromIterator<T>
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
Self::Mutable(Vec::from_iter(iter))
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> Deref
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
type Target = [T];
fn deref(&self) -> &Self::Target {
match self {
Self::Mutable(values) => values,
Self::Empty => &[],
Self::Frozen(values) => values.as_slice(),
}
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> DerefMut
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
fn deref_mut(&mut self) -> &mut Self::Target {
self.mutable()
}
}
impl<'a, T, const CAPACITY: usize, const SLOT_BYTES: usize> IntoIterator
for &'a PayloadVec<T, CAPACITY, SLOT_BYTES>
{
type Item = &'a T;
type IntoIter = std::slice::Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<T, const CAPACITY: usize, const SLOT_BYTES: usize> IntoIterator
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
type Item = T;
type IntoIter = std::vec::IntoIter<T>;
fn into_iter(self) -> Self::IntoIter {
self.into_boxed_slice().into_vec().into_iter()
}
}
impl<T: fmt::Debug, const CAPACITY: usize, const SLOT_BYTES: usize> fmt::Debug
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.deref().fmt(formatter)
}
}
impl<T: PartialEq, const CAPACITY: usize, const SLOT_BYTES: usize, const N: usize> PartialEq<[T; N]>
for PayloadVec<T, CAPACITY, SLOT_BYTES>
{
fn eq(&self, other: &[T; N]) -> bool {
self.deref() == other
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashSet;
use std::sync::{Arc, Barrier, Mutex};
use std::thread;
type TestVec = PayloadVec<u64, 16, 192>;
type TestOwner = PayloadVecSlabOwner<u64, 16, 192>;
fn frozen_index(values: &TestVec) -> usize {
match values {
PayloadVec::Frozen(values) => values.index,
PayloadVec::Mutable(_) | PayloadVec::Empty => panic!("test vector was not frozen"),
}
}
#[test]
fn frozen_vector_is_aligned_and_clone_is_a_private_candidate() {
let owner = TestOwner::new();
let frozen = owner.freeze(vec![1, 2, 3]);
let pointer = match &frozen {
PayloadVec::Frozen(values) => values.pointer.as_ptr() as usize,
PayloadVec::Mutable(_) | PayloadVec::Empty => unreachable!(),
};
assert_eq!(pointer % 64, 0);
assert_eq!(&*frozen, &[1, 2, 3]);
let mut candidate = frozen.clone();
assert!(matches!(candidate, PayloadVec::Mutable(_)));
candidate.push(4);
assert_eq!(&*candidate, &[1, 2, 3, 4]);
assert_eq!(&*frozen, &[1, 2, 3]);
}
#[test]
fn live_slot_is_not_reused_but_dropped_slot_is() {
let owner = TestOwner::new();
let first = owner.freeze(vec![1]);
let first_index = frozen_index(&first);
let second = owner.freeze(vec![2]);
assert_ne!(frozen_index(&second), first_index);
assert_eq!(owner.slots(), 2);
drop(first);
let reused = owner.freeze(vec![3]);
assert_eq!(frozen_index(&reused), first_index);
assert_eq!(owner.slots(), 2);
assert_eq!(owner.reused(), 1);
}
#[test]
fn frozen_vector_keeps_slab_alive_after_owner_drop() {
let frozen = {
let owner = TestOwner::new();
owner.freeze(vec![11, 22, 33])
};
assert_eq!(&*frozen, &[11, 22, 33]);
drop(frozen);
}
#[test]
fn consuming_frozen_vector_moves_each_element_once() {
let owner = TestOwner::new();
let frozen = owner.freeze(vec![7, 8, 9]);
let boxed = frozen.into_boxed_slice();
assert_eq!(&*boxed, &[7, 8, 9]);
assert_eq!(owner.live(), 0);
assert_eq!(owner.slots(), 1);
let reused = owner.freeze(vec![10]);
assert_eq!(frozen_index(&reused), 0);
}
#[test]
fn concurrent_freeze_and_drop_never_share_a_live_slot() {
const THREADS: usize = 8;
const ITERATIONS: usize = 10_000;
let owner = Arc::new(TestOwner::new());
let live = Arc::new(Mutex::new(HashSet::new()));
let start = Arc::new(Barrier::new(THREADS));
let mut workers = Vec::new();
for thread_index in 0..THREADS {
let owner = Arc::clone(&owner);
let live = Arc::clone(&live);
let start = Arc::clone(&start);
workers.push(thread::spawn(move || {
start.wait();
for iteration in 0..ITERATIONS {
let value = ((thread_index as u64) << 32) | iteration as u64;
let frozen = owner.freeze(vec![value]);
let index = frozen_index(&frozen);
assert!(live.lock().unwrap().insert(index));
thread::yield_now();
assert_eq!(frozen[0], value);
assert!(live.lock().unwrap().remove(&index));
drop(frozen);
}
}));
}
for worker in workers {
worker.join().unwrap();
}
assert!(live.lock().unwrap().is_empty());
assert_eq!(owner.live(), 0);
assert!(owner.slots() <= THREADS);
assert_eq!(owner.allocated_blocks(), 1);
assert!(owner.reused() >= (THREADS * (ITERATIONS - 1)) as u64);
}
#[test]
fn frozen_empty_vector_needs_no_vm_slot() {
let owner = TestOwner::new();
let empty = owner.freeze(Vec::new());
assert!(matches!(empty, PayloadVec::Empty));
assert!(empty.is_empty());
assert_eq!(owner.slots(), 0);
assert_eq!(owner.allocated_blocks(), 0);
let candidate = empty.clone();
assert!(matches!(candidate, PayloadVec::Mutable(_)));
}
}