use core::cell::Cell;
use core::fmt;
use core::marker::PhantomData;
use core::ptr::NonNull;
#[cfg(feature = "alloc")]
use alloc::{alloc::Layout, boxed::Box, vec::Vec};
#[cfg(feature = "alloc")]
use core::cell::RefCell;
#[cfg(feature = "alloc")]
use core::mem::MaybeUninit;
const MAX_ALIGN: usize = 16;
#[cfg(feature = "alloc")]
const DEFAULT_CHUNK: usize = 4096;
#[cfg(feature = "alloc")]
const MAX_CHUNK: usize = 96 * 1024;
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub struct ArenaExhausted;
#[cfg(feature = "alloc")]
struct Chunk {
storage: Option<NonNull<[MaybeUninit<u8>]>>,
data: NonNull<u8>,
limit: NonNull<u8>,
}
#[cfg(feature = "alloc")]
struct Grow {
head: Option<Chunk>, more: Vec<Chunk>, cursor: usize, next_chunk: usize, cap: usize, }
#[cfg(feature = "alloc")]
impl Grow {
fn chunk(&self, i: usize) -> Option<&Chunk> {
match i.checked_sub(1) {
None => self.head.as_ref(),
Some(j) => self.more.get(j),
}
}
}
pub struct Arena<'buf> {
cur: Cell<NonNull<u8>>,
limit: Cell<NonNull<u8>>,
start: Cell<NonNull<u8>>,
used: Cell<usize>,
reserved: Cell<usize>,
#[cfg(feature = "alloc")]
grow: RefCell<Grow>,
#[cfg(not(feature = "alloc"))]
seed: Cell<Option<(NonNull<u8>, NonNull<u8>)>>,
_marker: PhantomData<&'buf mut [u8]>,
}
unsafe impl Send for Arena<'_> {}
#[inline(always)]
fn align_pad(addr: usize, align: usize) -> usize {
debug_assert!(align.is_power_of_two());
addr.wrapping_neg() & (align - 1)
}
fn aligned_region(base: *mut u8, len: usize) -> Option<(NonNull<u8>, NonNull<u8>)> {
let pad = align_pad(base.addr(), MAX_ALIGN);
if pad >= len {
return None;
}
Some((
NonNull::new(base.wrapping_add(pad))?,
NonNull::new(base.wrapping_add(len))?,
))
}
impl<'buf> Arena<'buf> {
pub fn with_buffer(buf: &'buf mut [u8]) -> Self {
let region = if buf.len() > MAX_ALIGN {
aligned_region(buf.as_mut_ptr(), buf.len())
} else {
None
};
let dangling = NonNull::<u8>::dangling();
let (cur, limit) = region.unwrap_or((dangling, dangling));
let reserved = region.map_or(0, |(d, l)| l.as_ptr().addr() - d.as_ptr().addr());
Arena {
cur: Cell::new(cur),
limit: Cell::new(limit),
start: Cell::new(cur),
used: Cell::new(0),
reserved: Cell::new(reserved),
#[cfg(feature = "alloc")]
grow: RefCell::new(Grow {
head: region.map(|(data, limit)| Chunk {
storage: None,
data,
limit,
}),
more: Vec::new(),
cursor: 0,
next_chunk: DEFAULT_CHUNK,
cap: usize::MAX,
}),
#[cfg(not(feature = "alloc"))]
seed: Cell::new(region),
_marker: PhantomData,
}
}
#[doc(hidden)]
#[inline(always)]
pub fn alloc_bytes(&self, bytes: usize, align: usize) -> Result<NonNull<u8>, ArenaExhausted> {
if !align.is_power_of_two() {
return Err(ArenaExhausted);
}
if let Some(p) = self.try_bump(bytes, align) {
return Ok(p);
}
self.allocate_slow(bytes, align)
}
#[doc(hidden)]
#[allow(clippy::mut_from_ref)]
#[inline(always)]
pub fn emplace<T, E, F>(&self, f: F) -> Result<&mut T, E>
where
E: From<ArenaExhausted>,
F: for<'id> FnOnce(
crate::decode_slot::Slot<'id, T>,
) -> Result<crate::decode_slot::Init<'id>, E>,
{
let p = self
.alloc_bytes(core::mem::size_of::<T>(), core::mem::align_of::<T>())?
.cast::<T>();
let slot = unsafe { crate::decode_slot::Slot::new(p) };
let _init = f(slot)?;
Ok(unsafe { &mut *p.as_ptr() })
}
pub(crate) fn alloc_array<T>(&self, n: usize) -> Result<NonNull<T>, ArenaExhausted> {
let elem = core::mem::size_of::<T>();
if n == 0 || (elem != 0 && n > usize::MAX / elem) {
return Err(ArenaExhausted);
}
let p = self.alloc_bytes(n * elem, core::mem::align_of::<T>())?;
Ok(p.cast::<T>())
}
#[inline]
pub(crate) unsafe fn shrink_last(&self, ptr: NonNull<u8>, old_bytes: usize, new_bytes: usize) {
if new_bytes > old_bytes {
return;
}
let cur = self.cur.get();
let addr = ptr.as_ptr().addr();
if addr + old_bytes == cur.as_ptr().addr() && addr >= self.start.get().as_ptr().addr() {
self.cur.set(unsafe { cur.sub(old_bytes - new_bytes) });
self.used.set(self.used.get() - (old_bytes - new_bytes));
}
}
pub fn bytes_used(&self) -> usize {
self.used.get()
}
pub fn bytes_reserved(&self) -> usize {
self.reserved.get()
}
pub fn set_capacity_limit(&self, max_reserved_bytes: usize) {
#[cfg(feature = "alloc")]
{
self.grow.borrow_mut().cap = max_reserved_bytes;
}
#[cfg(not(feature = "alloc"))]
let _ = max_reserved_bytes;
}
pub fn reset(&mut self) {
self.used.set(0);
#[cfg(feature = "alloc")]
let first = {
let g = self.grow.get_mut();
g.cursor = 0;
g.head.as_ref().map(|head| (head.data, head.limit))
};
#[cfg(not(feature = "alloc"))]
let first = self.seed.get();
let d = NonNull::<u8>::dangling();
let (data, limit) = first.unwrap_or((d, d));
self.enter(data, limit);
}
fn enter(&self, data: NonNull<u8>, limit: NonNull<u8>) {
self.start.set(data);
self.cur.set(data);
self.limit.set(limit);
}
#[inline(always)]
fn try_bump(&self, bytes: usize, align: usize) -> Option<NonNull<u8>> {
let cur = self.cur.get();
let avail = self.limit.get().as_ptr().addr() - cur.as_ptr().addr();
let pad = align_pad(cur.as_ptr().addr(), align);
if pad > avail || bytes > avail - pad {
return None;
}
let (aligned, new_cur) = unsafe {
let aligned = cur.add(pad);
(aligned, aligned.add(bytes))
};
self.cur.set(new_cur);
self.used.set(self.used.get() + bytes);
Some(aligned)
}
#[cfg(not(feature = "alloc"))]
#[cold]
fn allocate_slow(&self, _bytes: usize, _align: usize) -> Result<NonNull<u8>, ArenaExhausted> {
Err(ArenaExhausted) }
#[cfg(feature = "alloc")]
#[cold]
#[inline(never)]
fn allocate_slow(&self, bytes: usize, align: usize) -> Result<NonNull<u8>, ArenaExhausted> {
{
let mut g = self.grow.borrow_mut();
let next = g
.chunk(g.cursor + 1)
.filter(|c| chunk_fits(c, bytes, align))
.map(|c| (c.data, c.limit));
if let Some((data, limit)) = next {
g.cursor += 1;
self.enter(data, limit);
} else {
self.grow_chunk(&mut g, bytes, align)?;
}
}
self.try_bump(bytes, align).ok_or(ArenaExhausted)
}
#[cfg(feature = "alloc")]
fn grow_chunk(&self, g: &mut Grow, bytes: usize, align: usize) -> Result<(), ArenaExhausted> {
let min_usable = bytes.checked_add(align).ok_or(ArenaExhausted)?;
let want = if g.next_chunk < min_usable {
min_usable
} else {
g.next_chunk
};
let raw = want.checked_add(MAX_ALIGN).ok_or(ArenaExhausted)?;
let layout = Layout::array::<MaybeUninit<u8>>(raw).map_err(|_| ArenaExhausted)?;
let reserved = self.reserved.get();
if reserved >= g.cap || raw > g.cap - reserved {
return Err(ArenaExhausted); }
if g.head.is_some() {
g.more.try_reserve(1).map_err(|_| ArenaExhausted)?;
}
let base = NonNull::new(unsafe { alloc::alloc::alloc(layout) }).ok_or(ArenaExhausted)?;
let (data, limit) = aligned_region(base.as_ptr(), raw).ok_or(ArenaExhausted)?;
let usable = limit.as_ptr().addr() - data.as_ptr().addr();
let chunk = Chunk {
storage: Some(NonNull::slice_from_raw_parts(base.cast(), raw)),
data,
limit,
};
if g.head.is_none() {
g.head = Some(chunk);
g.cursor = 0;
} else {
let at = g.cursor;
g.more.insert(at, chunk);
g.cursor += 1;
}
self.reserved.set(reserved + usable);
self.enter(data, limit);
if g.next_chunk < MAX_CHUNK {
g.next_chunk = (g.next_chunk << 1).min(MAX_CHUNK);
}
Ok(())
}
}
#[cfg(feature = "alloc")]
fn chunk_fits(c: &Chunk, bytes: usize, align: usize) -> bool {
let data = c.data.as_ptr();
let pad = align_pad(data.addr(), align);
let avail = c.limit.as_ptr().addr() - data.addr();
pad <= avail && bytes <= avail - pad
}
#[cfg(feature = "alloc")]
impl Arena<'static> {
pub fn new() -> Arena<'static> {
let dangling = NonNull::<u8>::dangling();
Arena {
cur: Cell::new(dangling),
limit: Cell::new(dangling),
start: Cell::new(dangling),
used: Cell::new(0),
reserved: Cell::new(0),
grow: RefCell::new(Grow {
head: None,
more: Vec::new(),
cursor: 0,
next_chunk: DEFAULT_CHUNK,
cap: usize::MAX,
}),
_marker: PhantomData,
}
}
}
#[cfg(feature = "alloc")]
impl Default for Arena<'static> {
fn default() -> Self {
Arena::new()
}
}
impl fmt::Debug for Arena<'_> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Arena")
.field("bytes_used", &self.bytes_used())
.field("bytes_reserved", &self.bytes_reserved())
.finish()
}
}
#[cfg(feature = "alloc")]
impl Drop for Arena<'_> {
fn drop(&mut self) {
let g = self.grow.get_mut();
for chunk in g.head.take().into_iter().chain(g.more.drain(..)) {
if let Some(storage) = chunk.storage {
drop(unsafe { Box::from_raw(storage.as_ptr()) });
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[allow(clippy::mut_from_ref)]
fn alloc<'a, T>(arena: &'a Arena<'_>, val: T) -> Result<&'a mut T, ArenaExhausted> {
arena.emplace(|slot| Ok(slot.write(val)))
}
fn assert_aligned(p: NonNull<u8>, align: usize) {
assert_eq!(p.as_ptr().addr() % align, 0, "mis-aligned allocation");
}
#[cfg(not(feature = "alloc"))]
#[repr(align(16))]
struct Aligned64([u8; 64]);
#[test]
fn alignment_is_honored() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
a.alloc_bytes(1, 1).unwrap(); for &align in &[1usize, 2, 4, 8, 16] {
let p = a.alloc_bytes(align, align).unwrap();
assert_aligned(p, align);
}
}
#[test]
fn debug_prints_usage() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
a.alloc_bytes(8, 8).unwrap();
let expected = format!(
"Arena {{ bytes_used: 8, bytes_reserved: {} }}",
a.bytes_reserved()
);
assert_eq!(format!("{a:?}"), expected);
}
#[cfg(not(feature = "alloc"))]
#[test]
fn no_alloc_exhaustion_is_an_error_not_a_panic() {
let mut backing = Aligned64([0u8; 64]);
let buf = &mut backing.0;
let lo = buf.as_mut_ptr().addr();
let hi = lo + buf.len();
let a = Arena::with_buffer(buf);
let mut handed_out = 0usize;
while let Ok(p) = a.alloc_bytes(8, 8) {
let addr = p.as_ptr().addr();
assert!(
addr >= lo && addr + 8 <= hi,
"allocation escaped the seed buffer"
);
handed_out += 1;
assert!(handed_out <= 8, "handed out more than the buffer can hold");
}
assert_eq!(handed_out, 8, "should fit exactly 8 aligned 8-byte cells");
}
#[test]
fn non_power_of_two_align_is_an_error_not_a_panic() {
let mut buf = [0u8; 64];
let a = Arena::with_buffer(&mut buf);
assert_eq!(a.alloc_bytes(8, 3), Err(ArenaExhausted));
assert_eq!(a.alloc_bytes(8, 0), Err(ArenaExhausted));
}
#[test]
fn writes_round_trip() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
let x: &mut u64 = alloc(&a, 0xDEAD_BEEF_1234_5678u64).unwrap();
let y: &mut u32 = alloc(&a, 0xA5A5_5A5Au32).unwrap();
assert_eq!(*x, 0xDEAD_BEEF_1234_5678);
assert_eq!(*y, 0xA5A5_5A5A);
*x = 1;
assert_eq!(*x, 1);
}
#[test]
fn bytes_used_tracks_payload_and_seed_is_reserved() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
assert!(a.bytes_reserved() >= 240); assert_eq!(a.bytes_used(), 0);
a.alloc_bytes(8, 8).unwrap();
a.alloc_bytes(16, 8).unwrap();
assert_eq!(a.bytes_used(), 24);
}
#[test]
fn shrink_last_reclaims_the_tail_of_the_last_alloc() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
let p = a.alloc_bytes(64, 1).unwrap();
assert_eq!(a.bytes_used(), 64);
unsafe { a.shrink_last(p, 64, 16) }; assert_eq!(a.bytes_used(), 16);
let q = a.alloc_bytes(8, 1).unwrap();
assert_eq!(q.as_ptr().addr(), p.as_ptr().addr() + 16);
}
#[test]
fn shrink_last_is_a_noop_when_not_the_last_alloc() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
let p = a.alloc_bytes(64, 1).unwrap();
let r = a.alloc_bytes(8, 1).unwrap();
unsafe { a.shrink_last(p, 64, 16) }; let s = a.alloc_bytes(8, 1).unwrap();
assert_eq!(
s.as_ptr().addr(),
r.as_ptr().addr() + 8,
"cursor must be untouched"
);
}
#[test]
fn shrink_last_rejects_growth_and_handles_zero() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
let p = a.alloc_bytes(32, 1).unwrap();
unsafe { a.shrink_last(p, 32, 48) }; let q = a.alloc_bytes(8, 1).unwrap();
assert_eq!(q.as_ptr().addr(), p.as_ptr().addr() + 32, "no-op on growth");
unsafe { a.shrink_last(q, 8, 0) }; let t = a.alloc_bytes(8, 1).unwrap();
assert_eq!(
t.as_ptr().addr(),
q.as_ptr().addr(),
"shrink-to-zero reclaims fully"
);
}
#[test]
fn reset_reuses_the_seed() {
let mut buf = [0u8; 64];
let mut a = Arena::with_buffer(&mut buf);
let first = a.alloc_bytes(8, 8).unwrap().as_ptr().addr();
a.alloc_bytes(8, 8).unwrap();
a.reset();
assert_eq!(a.bytes_used(), 0);
let after = a.alloc_bytes(8, 8).unwrap().as_ptr().addr();
assert_eq!(first, after, "reset should rewind to the seed base");
}
#[cfg(feature = "alloc")]
#[test]
fn heap_arena_grows_past_any_chunk() {
let a = Arena::new();
let mut last = 0usize;
for i in 0..5000 {
let p = alloc(&a, i as u64).unwrap();
assert_eq!(*p, i as u64);
last = *p as usize;
}
assert_eq!(last, 4999);
}
#[cfg(feature = "alloc")]
#[test]
fn seed_then_grow_is_seamless() {
let mut buf = [0u8; 16];
let a = Arena::with_buffer(&mut buf);
for i in 0..1000u64 {
assert!(alloc(&a, i).is_ok(), "seed→heap spill must be seamless");
}
}
#[cfg(feature = "alloc")]
#[test]
fn big_request_bigger_than_grow_step_succeeds() {
let a = Arena::new();
let p = a.alloc_bytes(1 << 20, 64).unwrap();
assert_aligned(p, 64);
}
#[cfg(all(feature = "alloc", target_pointer_width = "64"))]
#[cfg_attr(miri, ignore)] #[test]
fn host_allocation_failure_is_an_error_not_an_abort() {
let a = Arena::new();
assert_eq!(a.alloc_bytes(1 << 62, 1), Err(ArenaExhausted));
assert_eq!(a.alloc_bytes(usize::MAX - 64, 1), Err(ArenaExhausted));
assert!(a.alloc_bytes(64, 8).is_ok());
}
#[cfg(feature = "alloc")]
#[test]
fn seeded_arena_reset_rewinds_to_the_seed_and_reuses_grown_chunks() {
let mut buf = [0u8; 64];
let mut a = Arena::with_buffer(&mut buf);
let first = a.alloc_bytes(8, 8).unwrap().as_ptr().addr();
for i in 0..2000u64 {
alloc(&a, i).unwrap(); }
let reserved = a.bytes_reserved();
a.reset();
assert_eq!(a.alloc_bytes(8, 8).unwrap().as_ptr().addr(), first);
for i in 0..2000u64 {
alloc(&a, i).unwrap();
}
assert_eq!(
a.bytes_reserved(),
reserved,
"reused the held chunks without growing"
);
}
#[cfg(feature = "alloc")]
fn regrow_mid_list(mut a: Arena<'_>) {
for n in [4000, 8000, 16000] {
a.alloc_bytes(n, 1).unwrap();
}
a.reset();
a.alloc_bytes(4000, 1).unwrap();
let before = a.bytes_reserved();
a.alloc_bytes(30000, 1).unwrap(); let grown = a.bytes_reserved();
assert!(grown > before);
a.alloc_bytes(grown - before - 30000, 1).unwrap(); a.alloc_bytes(8000, 1).unwrap();
a.alloc_bytes(16000, 1).unwrap();
assert_eq!(
a.bytes_reserved(),
grown,
"reused the chunks behind the inserted one"
);
a.reset();
for n in [4000, 30000, 8000, 16000] {
a.alloc_bytes(n, 1).unwrap();
}
assert_eq!(a.bytes_reserved(), grown);
}
#[cfg(feature = "alloc")]
#[test]
fn a_grow_after_reset_inserts_the_chunk_mid_list() {
regrow_mid_list(Arena::new());
let mut buf = [0u8; 4200];
regrow_mid_list(Arena::with_buffer(&mut buf));
let mut tiny = [0u8; 16]; regrow_mid_list(Arena::with_buffer(&mut tiny));
}
#[cfg(feature = "alloc")]
#[test]
fn alloc_array_reserves_storage() {
let a = Arena::new();
let p = a.alloc_array::<u32>(4).unwrap();
assert_aligned(p.cast::<u8>(), core::mem::align_of::<u32>());
for i in 0..4 {
unsafe { p.as_ptr().add(i).write(i as u32 * 10) };
}
for i in 0..4 {
assert_eq!(unsafe { *p.as_ptr().add(i) }, i as u32 * 10);
}
assert_eq!(a.alloc_array::<u32>(0), Err(ArenaExhausted)); }
#[cfg(feature = "alloc")]
#[test]
fn capacity_limit_makes_growth_fail_cleanly() {
let a = Arena::new();
a.set_capacity_limit(8 * 1024); let mut total = 0usize;
let mut hit_cap = false;
for _ in 0..100_000 {
match a.alloc_bytes(64, 8) {
Ok(_) => total += 64,
Err(ArenaExhausted) => {
hit_cap = true;
break;
}
}
}
assert!(hit_cap, "the cap should eventually be reached");
assert!(
a.bytes_reserved() <= 8 * 1024,
"reserved must stay within the cap"
);
assert!(total > 0);
}
#[cfg(feature = "alloc")]
#[test]
fn reset_keeps_chunks_and_reserved() {
let a = Arena::new();
for i in 0..5000u64 {
alloc(&a, i).unwrap(); }
let reserved_before = a.bytes_reserved();
assert!(reserved_before > 0);
let mut a = a;
a.reset();
assert_eq!(a.bytes_used(), 0);
assert_eq!(
a.bytes_reserved(),
reserved_before,
"reset keeps chunks (no free), so reserved is unchanged"
);
for i in 0..5000u64 {
alloc(&a, i).unwrap();
}
assert_eq!(
a.bytes_reserved(),
reserved_before,
"reused the held chunks without growing"
);
}
#[test]
fn emplace_initializes_in_place_on_ok_and_abandons_on_err() {
let mut buf = [0u8; 64];
let a = Arena::with_buffer(&mut buf);
let r = a
.emplace::<u64, ArenaExhausted, _>(|slot| Ok(slot.write(0xABCD)))
.unwrap();
assert_eq!(*r, 0xABCD);
let e = a.emplace::<u64, ArenaExhausted, _>(|slot| {
slot.write(1);
Err(ArenaExhausted)
});
assert!(e.is_err());
}
#[test]
fn emplace_handles_a_zero_sized_type() {
let mut buf = [0u8; 8];
let a = Arena::with_buffer(&mut buf);
let r = a
.emplace::<(), ArenaExhausted, _>(|slot| Ok(slot.write(())))
.unwrap();
assert_eq!(*r, ());
}
#[cfg(feature = "alloc")]
#[test]
fn emplace_handles_a_zero_sized_type_from_a_dangling_cursor() {
let a = Arena::new();
let r = a
.emplace::<(), ArenaExhausted, _>(|slot| Ok(slot.write(())))
.unwrap();
assert_eq!(*r, ());
}
#[test]
fn decode_value_moves_out_on_ok_and_propagates_err() {
let v = crate::decode_value::<u64, ArenaExhausted, _>(|slot| Ok(slot.write(123))).unwrap();
assert_eq!(v, 123);
let e = crate::decode_value::<u64, ArenaExhausted, _>(|slot| {
slot.write(9);
Err(ArenaExhausted)
});
assert!(e.is_err());
}
#[cfg(feature = "alloc")]
#[test]
fn a_grown_arena_moves_to_another_thread() {
let mut a = Arena::new();
for i in 0..1000u64 {
alloc(&a, i).unwrap();
}
let held = a.bytes_reserved();
std::thread::spawn(move || {
a.reset();
let v = alloc(&a, 7u64).unwrap();
assert_eq!(*v, 7);
assert_eq!(a.bytes_reserved(), held);
})
.join()
.unwrap();
}
#[test]
fn a_seeded_arena_moves_to_another_thread() {
let mut buf = [0u8; 256];
let a = Arena::with_buffer(&mut buf);
alloc(&a, 1u64).unwrap();
std::thread::scope(|s| {
s.spawn(move || {
let v = alloc(&a, 2u64).unwrap();
assert_eq!(*v, 2);
assert_eq!(a.bytes_used(), 16);
});
});
}
}