#![doc = include_str!("../README.md")]
#![deny(missing_debug_implementations)]
#![deny(missing_docs)]
#![no_std]
#![cfg_attr(
feature = "allocator_api",
feature(allocator_api, nonnull_slice_from_raw_parts)
)]
#[doc(hidden)]
pub extern crate alloc as core_alloc;
#[cfg(feature = "boxed")]
pub mod boxed;
#[cfg(feature = "collections")]
pub mod collections;
mod alloc;
use core::cell::Cell;
use core::fmt::Display;
use core::iter;
use core::marker::PhantomData;
use core::mem;
use core::ptr::{self, NonNull};
use core::slice;
use core::str;
use core_alloc::alloc::{alloc, dealloc, Layout};
#[cfg(feature = "allocator_api")]
use core_alloc::alloc::{AllocError, Allocator};
pub use alloc::AllocErr;
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum AllocOrInitError<E> {
Alloc(AllocErr),
Init(E),
}
impl<E> From<AllocErr> for AllocOrInitError<E> {
fn from(e: AllocErr) -> Self {
Self::Alloc(e)
}
}
impl<E: Display> Display for AllocOrInitError<E> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
AllocOrInitError::Alloc(err) => err.fmt(f),
AllocOrInitError::Init(err) => write!(f, "initialization failed: {}", err),
}
}
}
#[derive(Debug)]
pub struct Bump {
current_chunk_footer: Cell<NonNull<ChunkFooter>>,
allocation_limit: Cell<Option<usize>>,
}
#[repr(C)]
#[derive(Debug)]
struct ChunkFooter {
data: NonNull<u8>,
layout: Layout,
prev: Cell<NonNull<ChunkFooter>>,
ptr: Cell<NonNull<u8>>,
allocated_bytes: usize,
}
#[repr(transparent)]
struct EmptyChunkFooter(ChunkFooter);
unsafe impl Sync for EmptyChunkFooter {}
static EMPTY_CHUNK: EmptyChunkFooter = EmptyChunkFooter(ChunkFooter {
layout: Layout::new::<ChunkFooter>(),
data: unsafe { NonNull::new_unchecked(&EMPTY_CHUNK as *const EmptyChunkFooter as *mut u8) },
ptr: Cell::new(unsafe {
NonNull::new_unchecked(&EMPTY_CHUNK as *const EmptyChunkFooter as *mut u8)
}),
prev: Cell::new(unsafe {
NonNull::new_unchecked(&EMPTY_CHUNK as *const EmptyChunkFooter as *mut ChunkFooter)
}),
allocated_bytes: 0,
});
impl EmptyChunkFooter {
fn get(&'static self) -> NonNull<ChunkFooter> {
unsafe { NonNull::new_unchecked(&self.0 as *const ChunkFooter as *mut ChunkFooter) }
}
}
impl ChunkFooter {
fn as_raw_parts(&self) -> (*const u8, usize) {
let data = self.data.as_ptr() as *const u8;
let ptr = self.ptr.get().as_ptr() as *const u8;
debug_assert!(data <= ptr);
debug_assert!(ptr <= self as *const ChunkFooter as *const u8);
let len = unsafe { (self as *const ChunkFooter as *const u8).offset_from(ptr) as usize };
(ptr, len)
}
fn is_empty(&self) -> bool {
ptr::eq(self, EMPTY_CHUNK.get().as_ptr())
}
}
impl Default for Bump {
fn default() -> Bump {
Bump::new()
}
}
impl Drop for Bump {
fn drop(&mut self) {
unsafe {
dealloc_chunk_list(self.current_chunk_footer.get());
}
}
}
#[inline]
unsafe fn dealloc_chunk_list(mut footer: NonNull<ChunkFooter>) {
while !footer.as_ref().is_empty() {
let f = footer;
footer = f.as_ref().prev.get();
dealloc(f.as_ref().data.as_ptr(), f.as_ref().layout);
}
}
unsafe impl Send for Bump {}
#[inline]
pub(crate) fn round_up_to(n: usize, divisor: usize) -> Option<usize> {
debug_assert!(divisor > 0);
debug_assert!(divisor.is_power_of_two());
Some(n.checked_add(divisor - 1)? & !(divisor - 1))
}
#[inline]
pub(crate) fn round_down_to(n: usize, divisor: usize) -> usize {
debug_assert!(divisor > 0);
debug_assert!(divisor.is_power_of_two());
n & !(divisor - 1)
}
const PAGE_STRATEGY_CUTOFF: usize = 0x1000;
const SUPPORTED_ITER_ALIGNMENT: usize = 16;
const CHUNK_ALIGN: usize = SUPPORTED_ITER_ALIGNMENT;
const FOOTER_SIZE: usize = mem::size_of::<ChunkFooter>();
const _FOOTER_ALIGN_ASSERTION: bool = mem::align_of::<ChunkFooter>() <= CHUNK_ALIGN;
const _: [(); _FOOTER_ALIGN_ASSERTION as usize] = [()];
const MALLOC_OVERHEAD: usize = 16;
const OVERHEAD: usize = (MALLOC_OVERHEAD + FOOTER_SIZE + (CHUNK_ALIGN - 1)) & !(CHUNK_ALIGN - 1);
const FIRST_ALLOCATION_GOAL: usize = 1 << 9;
const DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER: usize = FIRST_ALLOCATION_GOAL - OVERHEAD;
#[derive(Debug, Clone, Copy)]
struct NewChunkMemoryDetails {
new_size_without_footer: usize,
align: usize,
size: usize,
}
#[inline]
unsafe fn layout_from_size_align(size: usize, align: usize) -> Layout {
if cfg!(debug_assertions) {
Layout::from_size_align(size, align).unwrap()
} else {
Layout::from_size_align_unchecked(size, align)
}
}
#[inline(never)]
fn allocation_size_overflow<T>() -> T {
panic!("requested allocation size overflowed")
}
fn abs_diff(a: usize, b: usize) -> usize {
usize::max(a, b) - usize::min(a, b)
}
impl Bump {
pub fn new() -> Bump {
Self::with_capacity(0)
}
pub fn try_new() -> Result<Bump, AllocErr> {
Bump::try_with_capacity(0)
}
pub fn with_capacity(capacity: usize) -> Bump {
Bump::try_with_capacity(capacity).unwrap_or_else(|_| oom())
}
pub fn try_with_capacity(capacity: usize) -> Result<Self, AllocErr> {
if capacity == 0 {
return Ok(Bump {
current_chunk_footer: Cell::new(EMPTY_CHUNK.get()),
allocation_limit: Cell::new(None),
});
}
let layout = unsafe { layout_from_size_align(capacity, 1) };
let chunk_footer = unsafe {
Self::new_chunk(
Bump::new_chunk_memory_details(None, layout).ok_or(AllocErr)?,
layout,
EMPTY_CHUNK.get(),
)
.ok_or(AllocErr)?
};
Ok(Bump {
current_chunk_footer: Cell::new(chunk_footer),
allocation_limit: Cell::new(None),
})
}
pub fn allocation_limit(&self) -> Option<usize> {
self.allocation_limit.get()
}
pub fn set_allocation_limit(&self, limit: Option<usize>) {
self.allocation_limit.set(limit)
}
fn allocation_limit_remaining(&self) -> Option<usize> {
self.allocation_limit.get().and_then(|allocation_limit| {
let allocated_bytes = self.allocated_bytes();
if allocated_bytes > allocation_limit {
None
} else {
Some(abs_diff(allocation_limit, allocated_bytes))
}
})
}
fn chunk_fits_under_limit(
allocation_limit_remaining: Option<usize>,
new_chunk_memory_details: NewChunkMemoryDetails,
) -> bool {
allocation_limit_remaining
.map(|allocation_limit_left| {
allocation_limit_left >= new_chunk_memory_details.new_size_without_footer
})
.unwrap_or(true)
}
fn new_chunk_memory_details(
new_size_without_footer: Option<usize>,
requested_layout: Layout,
) -> Option<NewChunkMemoryDetails> {
let mut new_size_without_footer =
new_size_without_footer.unwrap_or(DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER);
let mut align = CHUNK_ALIGN;
align = align.max(requested_layout.align());
let requested_size =
round_up_to(requested_layout.size(), align).unwrap_or_else(allocation_size_overflow);
new_size_without_footer = new_size_without_footer.max(requested_size);
if new_size_without_footer < PAGE_STRATEGY_CUTOFF {
new_size_without_footer =
(new_size_without_footer + OVERHEAD).next_power_of_two() - OVERHEAD;
} else {
new_size_without_footer =
round_up_to(new_size_without_footer + OVERHEAD, 0x1000)? - OVERHEAD;
}
debug_assert_eq!(align % CHUNK_ALIGN, 0);
debug_assert_eq!(new_size_without_footer % CHUNK_ALIGN, 0);
let size = new_size_without_footer
.checked_add(FOOTER_SIZE)
.unwrap_or_else(allocation_size_overflow);
Some(NewChunkMemoryDetails {
new_size_without_footer,
size,
align,
})
}
unsafe fn new_chunk(
new_chunk_memory_details: NewChunkMemoryDetails,
requested_layout: Layout,
prev: NonNull<ChunkFooter>,
) -> Option<NonNull<ChunkFooter>> {
let NewChunkMemoryDetails {
new_size_without_footer,
align,
size,
} = new_chunk_memory_details;
let layout = layout_from_size_align(size, align);
debug_assert!(size >= requested_layout.size());
let data = alloc(layout);
let data = NonNull::new(data)?;
let footer_ptr = data.as_ptr().add(new_size_without_footer);
debug_assert_eq!((data.as_ptr() as usize) % align, 0);
debug_assert_eq!(footer_ptr as usize % CHUNK_ALIGN, 0);
let footer_ptr = footer_ptr as *mut ChunkFooter;
let ptr = Cell::new(NonNull::new_unchecked(footer_ptr as *mut u8));
let allocated_bytes = prev.as_ref().allocated_bytes + new_size_without_footer;
ptr::write(
footer_ptr,
ChunkFooter {
data,
layout,
prev: Cell::new(prev),
ptr,
allocated_bytes,
},
);
Some(NonNull::new_unchecked(footer_ptr))
}
pub fn reset(&mut self) {
unsafe {
if self.current_chunk_footer.get().as_ref().is_empty() {
return;
}
let mut cur_chunk = self.current_chunk_footer.get();
let prev_chunk = cur_chunk.as_ref().prev.replace(EMPTY_CHUNK.get());
dealloc_chunk_list(prev_chunk);
cur_chunk.as_ref().ptr.set(cur_chunk.cast());
cur_chunk.as_mut().allocated_bytes = cur_chunk.as_ref().layout.size();
debug_assert!(
self.current_chunk_footer
.get()
.as_ref()
.prev
.get()
.as_ref()
.is_empty(),
"We should only have a single chunk"
);
debug_assert_eq!(
self.current_chunk_footer.get().as_ref().ptr.get(),
self.current_chunk_footer.get().cast(),
"Our chunk's bump finger should be reset to the start of its allocation"
);
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc<T>(&self, val: T) -> &mut T {
self.alloc_with(|| val)
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn try_alloc<T>(&self, val: T) -> Result<&mut T, AllocErr> {
self.try_alloc_with(|| val)
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_with<F, T>(&self, f: F) -> &mut T
where
F: FnOnce() -> T,
{
#[inline(always)]
unsafe fn inner_writer<T, F>(ptr: *mut T, f: F)
where
F: FnOnce() -> T,
{
ptr::write(ptr, f())
}
let layout = Layout::new::<T>();
unsafe {
let p = self.alloc_layout(layout);
let p = p.as_ptr() as *mut T;
inner_writer(p, f);
&mut *p
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn try_alloc_with<F, T>(&self, f: F) -> Result<&mut T, AllocErr>
where
F: FnOnce() -> T,
{
#[inline(always)]
unsafe fn inner_writer<T, F>(ptr: *mut T, f: F)
where
F: FnOnce() -> T,
{
ptr::write(ptr, f())
}
let layout = Layout::new::<T>();
let p = self.try_alloc_layout(layout)?;
let p = p.as_ptr() as *mut T;
unsafe {
inner_writer(p, f);
Ok(&mut *p)
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_try_with<F, T, E>(&self, f: F) -> Result<&mut T, E>
where
F: FnOnce() -> Result<T, E>,
{
let rewind_footer = self.current_chunk_footer.get();
let rewind_ptr = unsafe { rewind_footer.as_ref() }.ptr.get();
let mut inner_result_ptr = NonNull::from(self.alloc_with(f));
match unsafe { inner_result_ptr.as_mut() } {
Ok(t) => Ok(unsafe {
&mut *(t as *mut _)
}),
Err(e) => unsafe {
if self.is_last_allocation(inner_result_ptr.cast()) {
let current_footer_p = self.current_chunk_footer.get();
let current_ptr = ¤t_footer_p.as_ref().ptr;
if current_footer_p == rewind_footer {
current_ptr.set(rewind_ptr);
} else {
current_ptr.set(current_footer_p.as_ref().data);
}
}
Err(ptr::read(e as *const _))
},
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn try_alloc_try_with<F, T, E>(&self, f: F) -> Result<&mut T, AllocOrInitError<E>>
where
F: FnOnce() -> Result<T, E>,
{
let rewind_footer = self.current_chunk_footer.get();
let rewind_ptr = unsafe { rewind_footer.as_ref() }.ptr.get();
let mut inner_result_ptr = NonNull::from(self.try_alloc_with(f)?);
match unsafe { inner_result_ptr.as_mut() } {
Ok(t) => Ok(unsafe {
&mut *(t as *mut _)
}),
Err(e) => unsafe {
if self.is_last_allocation(inner_result_ptr.cast()) {
let current_footer_p = self.current_chunk_footer.get();
let current_ptr = ¤t_footer_p.as_ref().ptr;
if current_footer_p == rewind_footer {
current_ptr.set(rewind_ptr);
} else {
current_ptr.set(current_footer_p.as_ref().data);
}
}
Err(AllocOrInitError::Init(ptr::read(e as *const _)))
},
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_slice_copy<T>(&self, src: &[T]) -> &mut [T]
where
T: Copy,
{
let layout = Layout::for_value(src);
let dst = self.alloc_layout(layout).cast::<T>();
unsafe {
ptr::copy_nonoverlapping(src.as_ptr(), dst.as_ptr(), src.len());
slice::from_raw_parts_mut(dst.as_ptr(), src.len())
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_slice_clone<T>(&self, src: &[T]) -> &mut [T]
where
T: Clone,
{
let layout = Layout::for_value(src);
let dst = self.alloc_layout(layout).cast::<T>();
unsafe {
for (i, val) in src.iter().cloned().enumerate() {
ptr::write(dst.as_ptr().add(i), val);
}
slice::from_raw_parts_mut(dst.as_ptr(), src.len())
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_str(&self, src: &str) -> &mut str {
let buffer = self.alloc_slice_copy(src.as_bytes());
unsafe {
str::from_utf8_unchecked_mut(buffer)
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_slice_fill_with<T, F>(&self, len: usize, mut f: F) -> &mut [T]
where
F: FnMut(usize) -> T,
{
let layout = Layout::array::<T>(len).unwrap_or_else(|_| oom());
let dst = self.alloc_layout(layout).cast::<T>();
unsafe {
for i in 0..len {
ptr::write(dst.as_ptr().add(i), f(i));
}
let result = slice::from_raw_parts_mut(dst.as_ptr(), len);
debug_assert_eq!(Layout::for_value(result), layout);
result
}
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_slice_fill_copy<T: Copy>(&self, len: usize, value: T) -> &mut [T] {
self.alloc_slice_fill_with(len, |_| value)
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_slice_fill_clone<T: Clone>(&self, len: usize, value: &T) -> &mut [T] {
self.alloc_slice_fill_with(len, |_| value.clone())
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_slice_fill_iter<T, I>(&self, iter: I) -> &mut [T]
where
I: IntoIterator<Item = T>,
I::IntoIter: ExactSizeIterator,
{
let mut iter = iter.into_iter();
self.alloc_slice_fill_with(iter.len(), |_| {
iter.next().expect("Iterator supplied too few elements")
})
}
#[inline(always)]
#[allow(clippy::mut_from_ref)]
pub fn alloc_slice_fill_default<T: Default>(&self, len: usize) -> &mut [T] {
self.alloc_slice_fill_with(len, |_| T::default())
}
#[inline(always)]
pub fn alloc_layout(&self, layout: Layout) -> NonNull<u8> {
self.try_alloc_layout(layout).unwrap_or_else(|_| oom())
}
#[inline(always)]
pub fn try_alloc_layout(&self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
if let Some(p) = self.try_alloc_layout_fast(layout) {
Ok(p)
} else {
self.alloc_layout_slow(layout).ok_or(AllocErr)
}
}
#[inline(always)]
fn try_alloc_layout_fast(&self, layout: Layout) -> Option<NonNull<u8>> {
unsafe {
let footer = self.current_chunk_footer.get();
let footer = footer.as_ref();
let ptr = footer.ptr.get().as_ptr();
let start = footer.data.as_ptr();
debug_assert!(start <= ptr);
debug_assert!(ptr as *const u8 <= footer as *const _ as *const u8);
if (ptr as usize) < layout.size() {
return None;
}
let ptr = ptr.wrapping_sub(layout.size());
let rem = ptr as usize % layout.align();
let aligned_ptr = ptr.wrapping_sub(rem);
if aligned_ptr >= start {
let aligned_ptr = NonNull::new_unchecked(aligned_ptr as *mut u8);
footer.ptr.set(aligned_ptr);
Some(aligned_ptr)
} else {
None
}
}
}
pub fn chunk_capacity(&self) -> usize {
let current_footer = self.current_chunk_footer.get();
let current_footer = unsafe { current_footer.as_ref() };
current_footer as *const _ as usize - current_footer.data.as_ptr() as usize
}
#[inline(never)]
fn alloc_layout_slow(&self, layout: Layout) -> Option<NonNull<u8>> {
unsafe {
let size = layout.size();
let allocation_limit_remaining = self.allocation_limit_remaining();
let current_footer = self.current_chunk_footer.get();
let current_layout = current_footer.as_ref().layout;
let min_new_chunk_size = layout.size().max(DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER);
let mut base_size = (current_layout.size() - FOOTER_SIZE)
.checked_mul(2)?
.max(min_new_chunk_size);
let chunk_memory_details = iter::from_fn(|| {
let bypass_min_chunk_size_for_small_limits = match self.allocation_limit() {
Some(limit)
if layout.size() < limit
&& base_size >= layout.size()
&& limit < DEFAULT_CHUNK_SIZE_WITHOUT_FOOTER
&& self.allocated_bytes() == 0 =>
{
true
}
_ => false,
};
if base_size >= min_new_chunk_size || bypass_min_chunk_size_for_small_limits {
let size = base_size;
base_size = base_size / 2;
Bump::new_chunk_memory_details(Some(size), layout)
} else {
None
}
});
let new_footer = chunk_memory_details
.filter_map(|chunk_memory_details| {
if Bump::chunk_fits_under_limit(
allocation_limit_remaining,
chunk_memory_details,
) {
Bump::new_chunk(chunk_memory_details, layout, current_footer)
} else {
None
}
})
.next()?;
debug_assert_eq!(
new_footer.as_ref().data.as_ptr() as usize % layout.align(),
0
);
self.current_chunk_footer.set(new_footer);
let new_footer = new_footer.as_ref();
let mut ptr = new_footer.ptr.get().as_ptr().sub(size);
ptr = ptr.sub(ptr as usize % layout.align());
debug_assert!(
ptr as *const _ <= new_footer,
"{:p} <= {:p}",
ptr,
new_footer
);
let ptr = NonNull::new_unchecked(ptr as *mut u8);
new_footer.ptr.set(ptr);
Some(ptr)
}
}
pub fn iter_allocated_chunks(&mut self) -> ChunkIter<'_> {
let raw = unsafe { self.iter_allocated_chunks_raw() };
ChunkIter {
raw,
bump: PhantomData,
}
}
pub unsafe fn iter_allocated_chunks_raw(&self) -> ChunkRawIter<'_> {
ChunkRawIter {
footer: self.current_chunk_footer.get(),
bump: PhantomData,
}
}
pub fn allocated_bytes(&self) -> usize {
let footer = self.current_chunk_footer.get();
unsafe { footer.as_ref().allocated_bytes }
}
#[inline]
unsafe fn is_last_allocation(&self, ptr: NonNull<u8>) -> bool {
let footer = self.current_chunk_footer.get();
let footer = footer.as_ref();
footer.ptr.get() == ptr
}
#[inline]
unsafe fn dealloc(&self, ptr: NonNull<u8>, layout: Layout) {
if self.is_last_allocation(ptr) {
let ptr = NonNull::new_unchecked(ptr.as_ptr().add(layout.size()));
self.current_chunk_footer.get().as_ref().ptr.set(ptr);
}
}
#[inline]
unsafe fn shrink(
&self,
ptr: NonNull<u8>,
old_layout: Layout,
new_layout: Layout,
) -> Result<NonNull<u8>, AllocErr> {
let old_size = old_layout.size();
let new_size = new_layout.size();
let align_is_compatible = old_layout.align() >= new_layout.align();
if !align_is_compatible {
return Err(AllocErr);
}
let delta = round_down_to(old_size - new_size, new_layout.align());
if self.is_last_allocation(ptr)
&& delta >= old_size / 2
{
let footer = self.current_chunk_footer.get();
let footer = footer.as_ref();
let new_ptr = NonNull::new_unchecked(footer.ptr.get().as_ptr().add(delta));
footer.ptr.set(new_ptr);
ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_ptr(), new_size);
return Ok(new_ptr);
} else {
return Ok(ptr);
}
}
#[inline]
unsafe fn grow(
&self,
ptr: NonNull<u8>,
old_layout: Layout,
new_layout: Layout,
) -> Result<NonNull<u8>, AllocErr> {
let old_size = old_layout.size();
let new_size = new_layout.size();
let align_is_compatible = old_layout.align() >= new_layout.align();
if align_is_compatible && self.is_last_allocation(ptr) {
let delta = new_size - old_size;
if let Some(p) =
self.try_alloc_layout_fast(layout_from_size_align(delta, old_layout.align()))
{
ptr::copy(ptr.as_ptr(), p.as_ptr(), old_size);
return Ok(p);
}
}
let new_ptr = self.try_alloc_layout(new_layout)?;
ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_ptr(), old_size);
Ok(new_ptr)
}
}
#[derive(Debug)]
pub struct ChunkIter<'a> {
raw: ChunkRawIter<'a>,
bump: PhantomData<&'a mut Bump>,
}
impl<'a> Iterator for ChunkIter<'a> {
type Item = &'a [mem::MaybeUninit<u8>];
fn next(&mut self) -> Option<&'a [mem::MaybeUninit<u8>]> {
unsafe {
let (ptr, len) = self.raw.next()?;
let slice = slice::from_raw_parts(ptr as *const mem::MaybeUninit<u8>, len);
Some(slice)
}
}
}
impl<'a> iter::FusedIterator for ChunkIter<'a> {}
#[derive(Debug)]
pub struct ChunkRawIter<'a> {
footer: NonNull<ChunkFooter>,
bump: PhantomData<&'a Bump>,
}
impl Iterator for ChunkRawIter<'_> {
type Item = (*mut u8, usize);
fn next(&mut self) -> Option<(*mut u8, usize)> {
unsafe {
let foot = self.footer.as_ref();
if foot.is_empty() {
return None;
}
let (ptr, len) = foot.as_raw_parts();
self.footer = foot.prev.get();
Some((ptr as *mut u8, len))
}
}
}
impl iter::FusedIterator for ChunkRawIter<'_> {}
#[inline(never)]
#[cold]
fn oom() -> ! {
panic!("out of memory")
}
unsafe impl<'a> alloc::Alloc for &'a Bump {
#[inline(always)]
unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
self.try_alloc_layout(layout)
}
#[inline]
unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
Bump::dealloc(self, ptr, layout)
}
#[inline]
unsafe fn realloc(
&mut self,
ptr: NonNull<u8>,
layout: Layout,
new_size: usize,
) -> Result<NonNull<u8>, AllocErr> {
let old_size = layout.size();
if old_size == 0 {
return self.try_alloc_layout(layout);
}
let new_layout = layout_from_size_align(new_size, layout.align());
if new_size <= old_size {
self.shrink(ptr, layout, new_layout)
} else {
self.grow(ptr, layout, new_layout)
}
}
}
#[cfg(feature = "allocator_api")]
unsafe impl<'a> Allocator for &'a Bump {
fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
self.try_alloc_layout(layout)
.map(|p| NonNull::slice_from_raw_parts(p, layout.size()))
.map_err(|_| AllocError)
}
unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
Bump::dealloc(self, ptr, layout)
}
unsafe fn shrink(
&self,
ptr: NonNull<u8>,
old_layout: Layout,
new_layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
Bump::shrink(self, ptr, old_layout, new_layout)
.map(|p| NonNull::slice_from_raw_parts(p, new_layout.size()))
.map_err(|_| AllocError)
}
unsafe fn grow(
&self,
ptr: NonNull<u8>,
old_layout: Layout,
new_layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
Bump::grow(self, ptr, old_layout, new_layout)
.map(|p| NonNull::slice_from_raw_parts(p, new_layout.size()))
.map_err(|_| AllocError)
}
unsafe fn grow_zeroed(
&self,
ptr: NonNull<u8>,
old_layout: Layout,
new_layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
let mut ptr = self.grow(ptr, old_layout, new_layout)?;
ptr.as_mut()[old_layout.size()..].fill(0);
Ok(ptr)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn chunk_footer_is_five_words() {
assert_eq!(mem::size_of::<ChunkFooter>(), mem::size_of::<usize>() * 6);
}
#[test]
#[allow(clippy::cognitive_complexity)]
fn test_realloc() {
use crate::alloc::Alloc;
unsafe {
const CAPACITY: usize = 1024 - OVERHEAD;
let mut b = Bump::with_capacity(CAPACITY);
let layout = Layout::from_size_align(100, 1).unwrap();
let p = b.alloc_layout(layout);
let q = (&b).realloc(p, layout, 51).unwrap();
assert_eq!(p, q);
b.reset();
let layout = Layout::from_size_align(100, 1).unwrap();
let p = b.alloc_layout(layout);
let q = (&b).realloc(p, layout, 50).unwrap();
assert!(p != q);
b.reset();
let layout = Layout::from_size_align(10, 1).unwrap();
let p = b.alloc_layout(layout);
let q = (&b).realloc(p, layout, 11).unwrap();
assert_eq!(q.as_ptr() as usize, p.as_ptr() as usize - 1);
b.reset();
let layout = Layout::from_size_align(1, 1).unwrap();
let p = b.alloc_layout(layout);
let q = (&b).realloc(p, layout, CAPACITY + 1).unwrap();
assert!(q.as_ptr() as usize != p.as_ptr() as usize - CAPACITY);
b = Bump::with_capacity(CAPACITY);
let layout = Layout::from_size_align(1, 1).unwrap();
let p = b.alloc_layout(layout);
let _ = b.alloc_layout(layout);
let q = (&b).realloc(p, layout, 2).unwrap();
assert!(q.as_ptr() as usize != p.as_ptr() as usize - 1);
b.reset();
}
}
#[test]
fn invalid_read() {
use alloc::Alloc;
let mut b = &Bump::new();
unsafe {
let l1 = Layout::from_size_align(12000, 4).unwrap();
let p1 = Alloc::alloc(&mut b, l1).unwrap();
let l2 = Layout::from_size_align(1000, 4).unwrap();
Alloc::alloc(&mut b, l2).unwrap();
let p1 = b.realloc(p1, l1, 24000).unwrap();
let l3 = Layout::from_size_align(24000, 4).unwrap();
b.realloc(p1, l3, 48000).unwrap();
}
}
}