#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
mod iter;
mod map;
mod node;
mod storage;
mod tree;
mod versioned_iter;
mod versioned_map;
mod versioned_tree;
use std::alloc::Layout;
use std::ptr::NonNull;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::Arc;
pub use iter::{ArenaEntryRef, Range};
pub use map::{ArenaArtMap, ArenaInserter};
pub use versioned_iter::{ArenaVersionedEntryRef, ArenaVersionedRange, VersionRef};
pub use versioned_map::{ArenaVersionedArtMap, ArenaVersionedInserter};
pub(crate) const ARENA_ALIGN: usize = 64;
pub const MAX_ARENA_SIZE: usize = (u32::MAX as usize) & !(ARENA_ALIGN - 1);
pub struct Arena {
id: u64,
cursor: AtomicU64,
base: NonNull<u8>,
raw: NonNull<u8>,
capacity: usize,
}
fn raw_layout(capacity: usize) -> Layout {
Layout::from_size_align(capacity + ARENA_ALIGN, std::mem::align_of::<u64>())
.expect("arena layout")
}
unsafe impl Send for Arena {}
unsafe impl Sync for Arena {}
fn next_arena_id() -> u64 {
static NEXT: AtomicU64 = AtomicU64::new(1);
NEXT.fetch_add(1, Ordering::Relaxed)
}
impl Arena {
pub fn new(capacity: usize) -> Self {
let capacity = capacity.clamp(ARENA_ALIGN, MAX_ARENA_SIZE) & !(ARENA_ALIGN - 1);
let layout = raw_layout(capacity);
let raw = NonNull::new(unsafe { std::alloc::alloc_zeroed(layout) })
.unwrap_or_else(|| std::alloc::handle_alloc_error(layout));
let pad = raw.as_ptr().align_offset(ARENA_ALIGN);
assert!(pad < ARENA_ALIGN, "arena base cannot be aligned");
let base = unsafe { raw.add(pad) };
Self {
id: next_arena_id(),
cursor: AtomicU64::new(ARENA_ALIGN as u64),
base,
raw,
capacity,
}
}
pub fn with_capacity(capacity: usize) -> Arc<Self> {
Arc::new(Self::new(capacity))
}
pub fn size(&self) -> usize {
(self.cursor.load(Ordering::Relaxed) as usize).min(self.capacity)
}
pub fn capacity(&self) -> usize {
self.capacity
}
pub fn remaining(&self) -> usize {
self.capacity - self.size()
}
pub fn is_empty(&self) -> bool {
self.cursor.load(Ordering::Relaxed) <= ARENA_ALIGN as u64
}
pub fn reset(&mut self) {
self.id = next_arena_id();
*self.cursor.get_mut() = ARENA_ALIGN as u64;
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn id(&self) -> u64 {
self.id
}
pub(crate) fn alloc(&self, layout: Layout) -> Option<u32> {
debug_assert!(layout.align() <= ARENA_ALIGN);
let align = layout.align() as u64;
let size = (layout.size() as u64).max(1);
if let Some(off) = tlab::take(self.id, align, size) {
return Some(off);
}
let mut cur = self.cursor.load(Ordering::Relaxed);
let mut contended = false;
loop {
let start = cur.checked_add(align - 1)? & !(align - 1);
let end = start.checked_add(size)?;
if end > self.capacity as u64 {
return None;
}
if contended {
if let Some(off) = self.refill(align, size, cur) {
return Some(off);
}
}
match self
.cursor
.compare_exchange_weak(cur, end, Ordering::Relaxed, Ordering::Relaxed)
{
Ok(_) => return Some(start as u32),
Err(actual) => {
contended |= actual != cur;
cur = actual;
}
}
}
}
fn refill(&self, align: u64, size: u64, mut cur: u64) -> Option<u32> {
const MAX_CHUNK: u64 = 16 * 1024;
loop {
let remaining = (self.capacity as u64).saturating_sub(cur);
let chunk = MAX_CHUNK.min(remaining / 32);
let start = cur.checked_add(ARENA_ALIGN as u64 - 1)? & !(ARENA_ALIGN as u64 - 1);
let end = start.checked_add(chunk)?;
if chunk < size + align || end > self.capacity as u64 {
return None;
}
match self
.cursor
.compare_exchange_weak(cur, end, Ordering::Relaxed, Ordering::Relaxed)
{
Ok(_) => {
tlab::install(self.id, start, end);
return tlab::take(self.id, align, size);
}
Err(actual) => cur = actual,
}
}
}
#[inline(always)]
pub(crate) unsafe fn ptr<T>(&self, offset: u32) -> NonNull<T> {
debug_assert!(offset as usize >= ARENA_ALIGN && (offset as usize) < self.capacity);
unsafe { self.base.add(offset as usize).cast::<T>() }
}
#[inline(always)]
pub(crate) fn offset_of<T>(&self, ptr: NonNull<T>) -> u32 {
let off = ptr.addr().get() - self.base.addr().get();
debug_assert!(off < self.capacity);
off as u32
}
}
mod tlab {
use std::cell::Cell;
const SLOTS: usize = 4;
#[derive(Copy, Clone)]
struct Slot {
arena: u64,
cur: u64,
end: u64,
}
const EMPTY: Slot = Slot {
arena: 0,
cur: 0,
end: 0,
};
std::thread_local! {
static SLOTS_TLS: Cell<[Slot; SLOTS]> = const { Cell::new([EMPTY; SLOTS]) };
}
pub(super) fn take(arena: u64, align: u64, size: u64) -> Option<u32> {
SLOTS_TLS
.try_with(|c| {
let mut slots = c.get();
let s = slots.iter_mut().find(|s| s.arena == arena)?;
let start = s.cur.checked_add(align - 1)? & !(align - 1);
let end = start.checked_add(size)?;
if end > s.end {
return None;
}
s.cur = end;
c.set(slots);
u32::try_from(start).ok()
})
.ok()
.flatten()
}
pub(super) fn install(arena: u64, start: u64, end: u64) {
SLOTS_TLS
.try_with(|c| {
let mut slots = c.get();
let i = slots
.iter()
.position(|s| s.arena == arena)
.or_else(|| slots.iter().position(|s| s.arena == 0))
.unwrap_or_else(|| {
(0..SLOTS)
.min_by_key(|&i| slots[i].end - slots[i].cur)
.unwrap_or(0)
});
slots[i] = Slot {
arena,
cur: start,
end,
};
c.set(slots);
})
.unwrap_or(());
}
}
impl Drop for Arena {
fn drop(&mut self) {
unsafe { std::alloc::dealloc(self.raw.as_ptr(), raw_layout(self.capacity)) }
}
}
impl std::fmt::Debug for Arena {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Arena")
.field("size", &self.size())
.field("capacity", &self.capacity)
.finish()
}
}
pub struct ArenaFull<K, V> {
pub key: K,
pub value: V,
}
impl<K, V> std::fmt::Debug for ArenaFull<K, V> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("ArenaFull")
}
}
impl<K, V> std::fmt::Display for ArenaFull<K, V> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("the arena is full")
}
}
impl<K, V> std::error::Error for ArenaFull<K, V> {}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
#[test]
fn tiny_and_zero_arenas_are_sound() {
for cap in [0, 1, 63, 64, 65, 4096] {
let a = Arena::new(cap);
assert!(a.capacity() >= ARENA_ALIGN);
assert_eq!(a.capacity() % ARENA_ALIGN, 0);
let r = a.alloc(Layout::new::<u64>());
assert_eq!(r.is_some(), a.capacity() > ARENA_ALIGN);
}
}
#[test]
fn allocations_are_aligned_bounded_and_never_advance_on_failure() {
let a = Arena::new(4096);
let o1 = a.alloc(Layout::new::<u8>()).unwrap();
let o2 = a.alloc(Layout::new::<u128>()).unwrap();
assert_eq!(o2 % 16, 0);
assert!(o2 > o1);
let o3 = a.alloc(Layout::from_size_align(8, 64).unwrap()).unwrap();
assert_eq!(o3 % 64, 0);
let before = a.size();
assert!(a
.alloc(Layout::from_size_align(1 << 20, 8).unwrap())
.is_none());
assert_eq!(a.size(), before, "a failed allocation does not advance");
while a.alloc(Layout::new::<u64>()).is_some() {}
assert!(a.remaining() < 8);
let a2 = Arena::new(4096);
let off = a2.alloc(Layout::new::<u64>()).unwrap();
let p = unsafe { a2.ptr::<u64>(off) };
assert_eq!(a2.offset_of(p), off);
assert_eq!(p.as_ptr().addr() % 8, 0);
}
#[test]
fn concurrent_allocations_never_overlap() {
let a = Arc::new(Arena::new(8 << 20));
let threads = if cfg!(miri) { 2 } else { 8 };
let per = if cfg!(miri) { 50 } else { 10_000 };
let hs: Vec<_> = (0..threads)
.map(|_| {
let a = Arc::clone(&a);
std::thread::spawn(move || {
(0..per)
.filter_map(|_| a.alloc(Layout::from_size_align(24, 8).unwrap()))
.collect::<Vec<_>>()
})
})
.collect();
let mut all: Vec<u32> = hs.into_iter().flat_map(|h| h.join().unwrap()).collect();
all.sort_unstable();
assert!(
all.windows(2).all(|w| w[1] - w[0] >= 24),
"overlapping allocations"
);
}
#[test]
fn reset_gives_a_fresh_identity() {
let mut a = Arena::new(1024);
let id = a.id();
a.alloc(Layout::new::<u64>()).unwrap();
a.reset();
assert!(a.is_empty());
assert_ne!(a.id(), id);
}
}