use std::cell::UnsafeCell;
use std::mem::MaybeUninit;
use std::num::NonZeroU64;
use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
use crossbeam_queue::ArrayQueue;
use crate::internal_protocol::segments::StableByteOwner;
const ACTIVE: u64 = 1;
const RELEASING: u64 = 2;
const STATE_GENERATION_SHIFT: u64 = 2;
const TOKEN_INDEX_BITS: u32 = 16;
const TOKEN_INDEX_MASK: u64 = u16::MAX as u64;
const MAX_GENERATION: u64 = (1 << (u64::BITS - TOKEN_INDEX_BITS)) - 1;
#[derive(Debug, Eq, Hash, PartialEq)]
pub(crate) struct StableOwnerToken(NonZeroU64);
impl StableOwnerToken {
fn new(index: usize, generation: u64) -> Self {
let index = u16::try_from(index).expect("stable owner pool has at most u16 slots");
assert!(generation <= MAX_GENERATION);
Self(
NonZeroU64::new((generation << TOKEN_INDEX_BITS) | u64::from(index))
.expect("stable owner generation is nonzero"),
)
}
fn index(&self) -> usize {
(self.0.get() & TOKEN_INDEX_MASK) as usize
}
fn generation(&self) -> u64 {
self.0.get() >> TOKEN_INDEX_BITS
}
}
pub(crate) trait StableByteOwnerPool: Send + Sync + 'static {
unsafe fn as_bytes(&self, token: &StableOwnerToken) -> &[u8];
unsafe fn release(&self, token: StableOwnerToken);
}
pub struct StableOwnerLease {
pool: Arc<dyn StableByteOwnerPool>,
token: Option<StableOwnerToken>,
}
impl std::fmt::Debug for StableOwnerLease {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
formatter
.debug_struct("StableOwnerLease")
.field("token", &self.token)
.finish_non_exhaustive()
}
}
impl StableOwnerLease {
fn new(pool: Arc<dyn StableByteOwnerPool>, token: StableOwnerToken) -> Self {
Self {
pool,
token: Some(token),
}
}
pub(crate) fn as_bytes(&self) -> &[u8] {
unsafe {
self.pool.as_bytes(
self.token
.as_ref()
.expect("stable owner lease retains a live token"),
)
}
}
}
impl Drop for StableOwnerLease {
fn drop(&mut self) {
if let Some(token) = self.token.take() {
unsafe { self.pool.release(token) };
}
}
}
struct Slot<T> {
state: AtomicU64,
value: UnsafeCell<MaybeUninit<T>>,
}
impl<T> Slot<T> {
fn new() -> Self {
Self {
state: AtomicU64::new(0),
value: UnsafeCell::new(MaybeUninit::uninit()),
}
}
}
unsafe impl<T: Send> Send for Slot<T> {}
unsafe impl<T: Send> Sync for Slot<T> {}
pub struct StableOwnerPool<T> {
slots: Box<[Slot<T>]>,
free_slots: Option<ArrayQueue<u16>>,
}
impl<T> StableOwnerPool<T> {
pub fn allocation_bytes(capacity: usize) -> Option<usize> {
let queue_slot_bytes = std::mem::size_of::<usize>()
.checked_add(std::mem::size_of::<u16>())?
.next_multiple_of(std::mem::align_of::<usize>());
std::mem::size_of::<Self>()
.checked_add(std::mem::size_of::<Slot<T>>().checked_mul(capacity)?)?
.checked_add(queue_slot_bytes.checked_mul(capacity)?)
}
pub fn new(capacity: usize) -> Arc<Self> {
assert!(
capacity <= TOKEN_INDEX_MASK as usize,
"stable owner pool capacity is too large"
);
let slots = (0..capacity)
.map(|_| Slot::new())
.collect::<Vec<_>>()
.into_boxed_slice();
let free_slots = (capacity != 0).then(|| {
let free_slots = ArrayQueue::new(capacity);
for index in 0..capacity {
free_slots
.push(index as u16)
.expect("stable owner free queue has fixed capacity");
}
free_slots
});
Arc::new(Self { slots, free_slots })
}
pub fn try_insert(self: &Arc<Self>, owner: T) -> Result<StableOwnerLease, T>
where
T: StableByteOwner,
{
let Some(index) = self.pop_free() else {
return Err(owner);
};
let slot = &self.slots[index];
let generation = (slot.state.load(Ordering::Relaxed) >> STATE_GENERATION_SHIFT)
.checked_add(1)
.filter(|generation| *generation <= MAX_GENERATION)
.expect("stable owner slot generation exhausted");
let active = (generation << STATE_GENERATION_SHIFT) | ACTIVE;
unsafe {
(*slot.value.get()).write(owner);
}
slot.state.store(active, Ordering::Release);
Ok(StableOwnerLease::new(
Arc::clone(self) as Arc<dyn StableByteOwnerPool>,
StableOwnerToken::new(index, generation),
))
}
fn pop_free(&self) -> Option<usize> {
self.free_slots.as_ref()?.pop().map(usize::from)
}
fn push_free(&self, index: usize) {
self.free_slots
.as_ref()
.expect("stable owner free queue exists for a live owner")
.push(u16::try_from(index).expect("stable owner pool index fits in u16"))
.expect("stable owner free queue exceeded its fixed capacity");
}
fn slot(&self, token: &StableOwnerToken) -> &Slot<T> {
self.slots
.get(token.index())
.expect("stable owner token index is valid")
}
}
impl<T> StableByteOwnerPool for StableOwnerPool<T>
where
T: StableByteOwner,
{
unsafe fn as_bytes(&self, token: &StableOwnerToken) -> &[u8] {
let slot = self.slot(token);
let expected = (token.generation() << STATE_GENERATION_SHIFT) | ACTIVE;
assert_eq!(
slot.state.load(Ordering::Acquire),
expected,
"stable owner token is not live"
);
unsafe { (*slot.value.get()).assume_init_ref().as_bytes() }
}
unsafe fn release(&self, token: StableOwnerToken) {
let slot = self.slot(&token);
let expected = (token.generation() << STATE_GENERATION_SHIFT) | ACTIVE;
let releasing = (token.generation() << STATE_GENERATION_SHIFT) | RELEASING;
assert!(
slot.state
.compare_exchange(expected, releasing, Ordering::AcqRel, Ordering::Acquire)
.is_ok(),
"stable owner token is not live"
);
unsafe { (*slot.value.get()).assume_init_drop() };
slot.state.store(
token.generation() << STATE_GENERATION_SHIFT,
Ordering::Release,
);
self.push_free(token.index());
}
}
impl<T> Drop for StableOwnerPool<T> {
fn drop(&mut self) {
for slot in self.slots.iter_mut() {
if slot.state.load(Ordering::Acquire) & ACTIVE == 0 {
continue;
}
unsafe { (*slot.value.get()).assume_init_drop() };
}
}
}