use core::ffi::c_void;
use core::sync::atomic::{AtomicBool, AtomicU32, AtomicUsize, Ordering};
use super::{Alloc, MemConfig, TlsDtor, align_up};
pub use super::PrimError;
const FERR: PrimError = 0xF13D;
pub const FERR_TOO_SMALL: PrimError = 0xF13E;
pub const FERR_GEOMETRY: PrimError = 0xF13F;
pub const FERR_REGISTERED: PrimError = 0xF140;
pub const FERR_MISALIGNED: PrimError = 0xF141;
pub const MIN_REGION: usize = crate::types::SEGMENT_SIZE;
pub const FIXED_PAGE: usize = 4096;
pub const REGION_ALIGN: usize = if cfg!(ra_aligned_region) {
crate::types::SEGMENT_SIZE
} else {
crate::types::MAX_ALIGN_SIZE
};
const _: () = assert!(
core::mem::align_of::<crate::segment::Segment>() <= REGION_ALIGN
&& core::mem::align_of::<crate::init::HeapBox>() <= REGION_ALIGN,
"a stride from a REGION_ALIGN-aligned base must satisfy every header"
);
const MAX_EXTENTS: usize = if cfg!(ra_max_extents = "8") {
8
} else if cfg!(ra_max_extents = "16") {
16
} else if cfg!(ra_max_extents = "64") {
64
} else {
32
};
static REGION_BASE: AtomicUsize = AtomicUsize::new(0);
static REGION_LEN: AtomicUsize = AtomicUsize::new(0);
static EXT_BASE: [AtomicUsize; MAX_EXTENTS] = [const { AtomicUsize::new(0) }; MAX_EXTENTS];
static EXT_LEN: [AtomicUsize; MAX_EXTENTS] = [const { AtomicUsize::new(0) }; MAX_EXTENTS];
static EXT_COUNT: AtomicUsize = AtomicUsize::new(0);
static LOCK: AtomicBool = AtomicBool::new(false);
struct Guard(&'static AtomicBool);
impl Guard {
fn acquire(lock: &'static AtomicBool) -> Self {
while lock
.compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed)
.is_err()
{
#[cfg(ra_single_threaded)]
if lock.load(Ordering::Relaxed) {
reentered();
}
core::hint::spin_loop();
}
Self(lock)
}
}
#[cfg(ra_single_threaded)]
#[cold]
#[inline(never)]
fn reentered() -> ! {
panic!(
"rusty_alloc: the allocator was re-entered. On a target built with \
--cfg ra_single_threaded nothing else can hold this lock, so this is \
almost certainly an interrupt handler that allocated while the main \
context was inside the allocator. prim::fixed's lock is NOT \
reentrant: do not allocate in an ISR. Note that ra_single_threaded \
means single CONTEXT, and an interrupt handler is a second context on \
one core."
)
}
impl Drop for Guard {
fn drop(&mut self) {
self.0.store(false, Ordering::Release);
}
}
#[must_use]
pub const fn usable_bytes(base: usize, len: usize) -> usize {
let seg = crate::types::SEGMENT_SIZE;
let Some(end) = base.checked_add(len) else {
return 0;
};
let Some(run_up) = base.checked_add(REGION_ALIGN - 1) else {
return 0;
};
let first = run_up & !(REGION_ALIGN - 1);
if first >= end {
return 0;
}
let avail = end - first;
(avail / seg) * seg
}
#[must_use]
pub const fn good_region_size(budget: usize) -> usize {
let seg = crate::types::SEGMENT_SIZE;
(budget / seg) * seg
}
#[must_use]
pub const fn region_for(usable: usize) -> usize {
let seg = crate::types::SEGMENT_SIZE;
let segments = if usable == 0 { 1 } else { usable.div_ceil(seg) };
segments * seg
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub struct Shape {
pub page_bytes: usize,
pub dedicated_segments: usize,
pub direct_route: bool,
}
#[must_use]
pub const fn shape_of(size: usize) -> Shape {
use crate::types::{
LARGE_OBJ_SIZE_MAX, MEDIUM_OBJ_SIZE_MAX, MEDIUM_PAGE_SIZE, SEGMENT_SLICE_SIZE,
SMALL_OBJ_SIZE_MAX, SMALL_PAGE_SIZE, SMALL_SIZE_MAX,
};
let dedicated = dedicated_segments(size);
let page_bytes = if size <= SMALL_OBJ_SIZE_MAX {
SMALL_PAGE_SIZE
} else if size <= MEDIUM_OBJ_SIZE_MAX {
MEDIUM_PAGE_SIZE
} else if size <= LARGE_OBJ_SIZE_MAX {
size.div_ceil(SEGMENT_SLICE_SIZE) * SEGMENT_SLICE_SIZE
} else {
dedicated * crate::types::SEGMENT_SIZE
};
Shape {
page_bytes,
dedicated_segments: dedicated,
direct_route: size <= SMALL_SIZE_MAX,
}
}
pub const LARGEST_SHARED_ALLOC: usize = crate::types::LARGE_OBJ_SIZE_MAX;
#[must_use]
pub const fn dedicated_segments(size: usize) -> usize {
if size <= LARGEST_SHARED_ALLOC {
return 0;
}
(crate::types::SEGMENT_SLICE_SIZE + size).div_ceil(crate::types::SEGMENT_SIZE)
}
#[must_use]
pub const fn region_for_allocs(size: usize, count: usize) -> usize {
let seg = crate::types::SEGMENT_SIZE;
let usable_slices = crate::types::SLICES_PER_SEGMENT - 1;
let dedicated = dedicated_segments(size);
let segments = if dedicated == 0 {
let slices_each = if size == 0 {
1
} else {
size.div_ceil(crate::types::SEGMENT_SLICE_SIZE)
};
let total = match slices_each.checked_mul(count) {
Some(n) => match n.checked_add(1) {
Some(n) => n,
None => return 0,
},
None => return 0,
};
total.div_ceil(usable_slices)
} else {
match dedicated.checked_mul(count) {
Some(n) => match n.checked_add(1) {
Some(n) => n,
None => return 0,
},
None => return 0,
}
};
let segments = if segments == 0 { 1 } else { segments };
match segments.checked_mul(seg) {
Some(bytes) => bytes,
None => 0,
}
}
pub fn init_region(region: &'static mut [u8]) -> Result<(), PrimError> {
let len = region.len();
if len < FIXED_PAGE {
return Err(FERR_TOO_SMALL);
}
let base = region.as_mut_ptr().expose_provenance();
if usable_bytes(base, len) == 0 {
return Err(FERR_GEOMETRY);
}
if usable_bytes(base, len) < usable_bytes(0, len) {
return Err(FERR_MISALIGNED);
}
let _g = Guard::acquire(&LOCK);
if REGION_LEN.load(Ordering::Relaxed) != 0 {
return Err(FERR_REGISTERED);
}
install_region(base, len);
Ok(())
}
fn install_region(base: usize, len: usize) {
let origin = if cfg!(ra_aligned_region) {
base
} else {
align_up(base, REGION_ALIGN)
};
let len = (base + len).saturating_sub(origin);
REGION_BASE.store(origin, Ordering::Relaxed);
REGION_LEN.store(len, Ordering::Relaxed);
EXT_BASE[0].store(origin, Ordering::Relaxed);
EXT_LEN[0].store(len, Ordering::Relaxed);
EXT_COUNT.store(1, Ordering::Relaxed);
}
#[cfg(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32")))]
struct FirstHeapBox(core::cell::UnsafeCell<core::mem::MaybeUninit<crate::init::HeapBox>>);
#[cfg(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32")))]
unsafe impl Sync for FirstHeapBox {}
#[cfg(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32")))]
static FIRST_HEAP_BOX: FirstHeapBox =
FirstHeapBox(core::cell::UnsafeCell::new(core::mem::MaybeUninit::uninit()));
#[cfg(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32")))]
static FIRST_HEAP_BOX_TAKEN: AtomicBool = AtomicBool::new(false);
#[must_use]
pub fn take_first_heap_box() -> Option<*mut crate::init::HeapBox> {
#[cfg(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32")))]
{
if FIRST_HEAP_BOX_TAKEN.swap(true, Ordering::AcqRel) {
None
} else {
Some(FIRST_HEAP_BOX.0.get().cast())
}
}
#[cfg(not(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32"))))]
{
None
}
}
#[must_use]
pub fn is_first_heap_box(hb: *const crate::init::HeapBox) -> bool {
#[cfg(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32")))]
{
core::ptr::eq(hb, FIRST_HEAP_BOX.0.get().cast_const().cast())
}
#[cfg(not(all(not(miri), not(windows), not(unix), not(target_arch = "wasm32"))))]
{
let _ = hb;
false
}
}
#[repr(C)]
#[cfg_attr(not(ra_aligned_region), repr(align(16)))]
#[cfg_attr(all(ra_aligned_region, ra_small_profile), repr(align(65536)))]
#[cfg_attr(all(ra_aligned_region, not(ra_small_profile)), repr(align(33554432)))]
pub struct Region<const N: usize> {
bytes: core::cell::UnsafeCell<[u8; N]>,
}
static REGION_GIVEN: AtomicBool = AtomicBool::new(false);
const _: () = assert!(
core::mem::align_of::<Region<MIN_REGION>>() == REGION_ALIGN,
"Region's alignment must equal REGION_ALIGN"
);
const _: () = assert!(
core::mem::size_of::<Region<MIN_REGION>>() == MIN_REGION,
"Region must carry no padding"
);
unsafe impl<const N: usize> Sync for Region<N> {}
impl<const N: usize> Region<N> {
pub const USABLE: usize = usable_bytes(0, N);
#[must_use]
pub const fn new() -> Self {
const {
assert!(
N >= MIN_REGION,
"Region<N>: N cannot hold one segment at this geometry - raise it, \
or set --cfg ra_small_profile (64 KiB segments)"
);
assert!(
N.is_multiple_of(crate::types::SEGMENT_SIZE),
"Region<N>: N must be a whole number of segments - size it with \
good_region_size(budget) or region_for(usable)"
);
}
Region {
bytes: core::cell::UnsafeCell::new([0; N]),
}
}
pub fn give(&'static self) -> Result<usize, PrimError> {
if REGION_GIVEN.swap(true, Ordering::AcqRel) {
return Err(FERR_REGISTERED);
}
let bytes: &'static mut [u8] = unsafe { &mut *self.bytes.get() };
let base = bytes.as_ptr().expose_provenance();
init_region(bytes)?;
Ok(usable_bytes(base, N))
}
#[must_use]
pub fn usable(&self) -> usize {
usable_bytes(self.bytes.get().expose_provenance(), N)
}
#[must_use]
pub const fn len(&self) -> usize {
N
}
#[must_use]
pub const fn is_empty(&self) -> bool {
N == 0
}
}
impl<const N: usize> Default for Region<N> {
fn default() -> Self {
Self::new()
}
}
#[must_use]
pub fn region_contains(addr: usize) -> bool {
let base = REGION_BASE.load(Ordering::Relaxed);
let len = REGION_LEN.load(Ordering::Relaxed);
len != 0 && addr >= base && addr - base < len
}
#[inline]
fn stride_origin() -> usize {
if cfg!(ra_aligned_region) {
0
} else {
REGION_BASE.load(Ordering::Relaxed)
}
}
#[inline]
pub(crate) fn stride_base() -> usize {
REGION_BASE.load(Ordering::Relaxed)
}
#[must_use]
pub fn region_stats() -> (usize, usize, usize) {
let _g = Guard::acquire(&LOCK);
let total = REGION_LEN.load(Ordering::Relaxed);
let free: usize = (0..EXT_COUNT.load(Ordering::Relaxed))
.map(|i| EXT_LEN[i].load(Ordering::Relaxed))
.sum();
(total - free, free, total)
}
#[must_use]
pub fn region_capacity() -> (usize, usize) {
let _g = Guard::acquire(&LOCK);
let seg = crate::types::SEGMENT_SIZE;
let origin = stride_origin();
let mut segments = 0usize;
let mut largest = 0usize;
for i in 0..EXT_COUNT.load(Ordering::Relaxed) {
let base = EXT_BASE[i].load(Ordering::Relaxed);
let len = EXT_LEN[i].load(Ordering::Relaxed);
let end = base + len;
let first = origin + (base - origin).next_multiple_of(seg);
if first >= end {
continue;
}
let run = end - first;
segments += run / seg;
if run > crate::types::SEGMENT_SLICE_SIZE {
let placeable = run - crate::types::SEGMENT_SLICE_SIZE;
if placeable > largest {
largest = placeable;
}
}
}
(segments, largest)
}
fn remove_at(idx: usize) {
let n = EXT_COUNT.load(Ordering::Relaxed);
for i in idx..n - 1 {
EXT_BASE[i].store(EXT_BASE[i + 1].load(Ordering::Relaxed), Ordering::Relaxed);
EXT_LEN[i].store(EXT_LEN[i + 1].load(Ordering::Relaxed), Ordering::Relaxed);
}
EXT_COUNT.store(n - 1, Ordering::Relaxed);
}
fn insert_at(idx: usize, base: usize, len: usize) {
let n = EXT_COUNT.load(Ordering::Relaxed);
let mut i = n;
while i > idx {
EXT_BASE[i].store(EXT_BASE[i - 1].load(Ordering::Relaxed), Ordering::Relaxed);
EXT_LEN[i].store(EXT_LEN[i - 1].load(Ordering::Relaxed), Ordering::Relaxed);
i -= 1;
}
EXT_BASE[idx].store(base, Ordering::Relaxed);
EXT_LEN[idx].store(len, Ordering::Relaxed);
EXT_COUNT.store(n + 1, Ordering::Relaxed);
}
const _: () = assert!(
crate::types::SEGMENT_SLICE_SIZE >= FIXED_PAGE,
"SEGMENT_SLICE_SIZE must be >= FIXED_PAGE or good_size over-promises"
);
pub(super) fn mem_init() -> MemConfig {
MemConfig {
page_size: FIXED_PAGE,
alloc_granularity: FIXED_PAGE,
large_page_size: 0,
has_overcommit: false,
has_partial_free: true,
}
}
fn place(
base: usize,
len: usize,
size: usize,
align: usize,
from_top: bool,
origin: usize,
) -> Option<usize> {
if size > len {
return None;
}
debug_assert!(base >= origin, "an extent lies inside the region");
let at = if from_top {
origin + ((base + len - size - origin) & !(align - 1))
} else {
origin + align_up(base - origin, align)
};
if at < base || at.saturating_add(size) > base + len {
return None;
}
Some(at)
}
pub(super) unsafe fn alloc(
size: usize,
try_alignment: usize,
_commit: bool,
_allow_large: bool,
) -> Result<Alloc, PrimError> {
if size == 0 {
return Err(FERR);
}
let align = try_alignment.max(FIXED_PAGE);
let size = align_up(size, FIXED_PAGE);
let _g = Guard::acquire(&LOCK);
if REGION_LEN.load(Ordering::Relaxed) == 0 {
return Err(FERR);
}
let origin = stride_origin();
let from_top = align == FIXED_PAGE;
let n = EXT_COUNT.load(Ordering::Relaxed);
for k in 0..n {
let i = if from_top { n - 1 - k } else { k };
let base = EXT_BASE[i].load(Ordering::Relaxed);
let len = EXT_LEN[i].load(Ordering::Relaxed);
let Some(aligned) = place(base, len, size, align, from_top, origin) else {
continue;
};
let head = aligned - base;
let tail = (base + len) - (aligned + size);
if head > 0 && tail > 0 && n + 1 > MAX_EXTENTS {
return Err(FERR);
}
remove_at(i);
let mut at = i;
if head > 0 {
insert_at(at, base, head);
at += 1;
}
if tail > 0 {
insert_at(at, aligned + size, tail);
}
return Ok(Alloc {
ptr: core::ptr::with_exposed_provenance_mut(aligned),
is_large: false,
is_zero: false,
});
}
Err(FERR)
}
pub(super) unsafe fn free(ptr: *mut u8, size: usize) -> Result<(), PrimError> {
if size == 0 {
return Ok(());
}
let base = ptr.expose_provenance();
let size = align_up(size, FIXED_PAGE);
let _g = Guard::acquire(&LOCK);
let rbase = REGION_BASE.load(Ordering::Relaxed);
let rlen = REGION_LEN.load(Ordering::Relaxed);
if rlen == 0 || base < rbase || base + size > rbase + rlen {
return Err(FERR);
}
let n = EXT_COUNT.load(Ordering::Relaxed);
let idx = EXT_BASE[..n]
.iter()
.position(|e| e.load(Ordering::Relaxed) > base)
.unwrap_or(n);
let prev_touches = idx > 0 && {
let pb = EXT_BASE[idx - 1].load(Ordering::Relaxed);
pb + EXT_LEN[idx - 1].load(Ordering::Relaxed) == base
};
let next_touches = idx < n && EXT_BASE[idx].load(Ordering::Relaxed) == base + size;
match (prev_touches, next_touches) {
(true, true) => {
let grown = EXT_LEN[idx - 1].load(Ordering::Relaxed)
+ size
+ EXT_LEN[idx].load(Ordering::Relaxed);
EXT_LEN[idx - 1].store(grown, Ordering::Relaxed);
remove_at(idx);
}
(true, false) => {
let grown = EXT_LEN[idx - 1].load(Ordering::Relaxed) + size;
EXT_LEN[idx - 1].store(grown, Ordering::Relaxed);
}
(false, true) => {
EXT_BASE[idx].store(base, Ordering::Relaxed);
let grown = EXT_LEN[idx].load(Ordering::Relaxed) + size;
EXT_LEN[idx].store(grown, Ordering::Relaxed);
}
(false, false) => {
if n >= MAX_EXTENTS {
return Err(FERR);
}
insert_at(idx, base, size);
}
}
Ok(())
}
#[allow(
clippy::unnecessary_wraps,
reason = "the prim backends share one signature; a no-op backend still returns the contract's Result"
)]
pub(super) unsafe fn commit(_ptr: *mut u8, _size: usize) -> Result<bool, PrimError> {
Ok(false)
}
#[allow(
clippy::unnecessary_wraps,
reason = "the prim backends share one signature; a no-op backend still returns the contract's Result"
)]
pub(super) unsafe fn decommit(_ptr: *mut u8, _size: usize) -> Result<bool, PrimError> {
Ok(false)
}
#[allow(
clippy::unnecessary_wraps,
reason = "the prim backends share one signature; a no-op backend still returns the contract's Result"
)]
pub(super) unsafe fn reset(_ptr: *mut u8, _size: usize) -> Result<(), PrimError> {
Ok(())
}
pub(super) unsafe fn protect(_ptr: *mut u8, _size: usize, _on: bool) -> Result<(), PrimError> {
Err(FERR)
}
pub(super) fn numa_node_count() -> usize {
1
}
#[inline]
pub(super) fn thread_id() -> usize {
1
}
static CLOCK_LOCK: AtomicBool = AtomicBool::new(false);
static TICK_LO: AtomicU32 = AtomicU32::new(0);
static TICK_HI: AtomicU32 = AtomicU32::new(0);
pub(super) fn clock_now() -> u64 {
let _g = Guard::acquire(&CLOCK_LOCK);
let (lo, carry) = TICK_LO.load(Ordering::Relaxed).overflowing_add(1);
TICK_LO.store(lo, Ordering::Relaxed);
let hi = if carry {
let h = TICK_HI.load(Ordering::Relaxed).wrapping_add(1);
TICK_HI.store(h, Ordering::Relaxed);
h
} else {
TICK_HI.load(Ordering::Relaxed)
};
(u64::from(hi) << 32) | u64::from(lo)
}
const MAX_TLS: usize = 8;
static TLS_VALUES: [AtomicUsize; MAX_TLS] = [const { AtomicUsize::new(0) }; MAX_TLS];
static NEXT_SLOT: AtomicUsize = AtomicUsize::new(0);
pub(super) struct TlsSlotImpl(usize);
pub(super) fn tls_new(_dtor: Option<TlsDtor>) -> Option<TlsSlotImpl> {
let idx = NEXT_SLOT.fetch_add(1, Ordering::Relaxed);
if idx < MAX_TLS {
Some(TlsSlotImpl(idx))
} else {
None
}
}
pub(super) fn tls_get(slot: &TlsSlotImpl) -> *mut c_void {
core::ptr::with_exposed_provenance_mut(TLS_VALUES[slot.0].load(Ordering::Relaxed))
}
pub(super) fn tls_set(slot: &TlsSlotImpl, value: *mut c_void) {
TLS_VALUES[slot.0].store(value.expose_provenance(), Ordering::Relaxed);
}
pub(super) fn tls_raw(slot: &TlsSlotImpl) -> usize {
slot.0
}
pub(super) fn tls_from_raw(raw: usize) -> TlsSlotImpl {
TlsSlotImpl(raw)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::types::SEGMENT_SIZE;
const _: () = assert!(super::super::FREE_RETURNS_MEMORY);
fn extents() -> Vec<(usize, usize)> {
let _g = Guard::acquire(&LOCK);
let rbase = REGION_BASE.load(Ordering::Relaxed);
(0..EXT_COUNT.load(Ordering::Relaxed))
.map(|i| {
(
EXT_BASE[i].load(Ordering::Relaxed) - rbase,
EXT_LEN[i].load(Ordering::Relaxed),
)
})
.collect()
}
fn free_total() -> usize {
extents().iter().map(|e| e.1).sum()
}
const GRID: usize = 64 * 1024;
const RAGGED: usize = if cfg!(ra_aligned_region) { 0 } else { 0x1f0 };
const SLACK: usize = GRID + RAGGED;
const N: usize = 512 * 1024 + FIXED_PAGE;
static mut BACKING: [u8; N + SLACK] = [0; N + SLACK];
static mut OTHER: [u8; FIXED_PAGE] = [0; FIXED_PAGE];
#[test]
fn serves_and_recycles_a_static_region() {
let bp = (&raw mut BACKING).cast::<u8>();
let skip = align_up(bp.expose_provenance(), GRID) - bp.expose_provenance() + RAGGED;
let rp = unsafe { bp.add(skip) };
assert_eq!(
rp.expose_provenance() % REGION_ALIGN,
0,
"on the grid the base needs"
);
assert_eq!(
rp.expose_provenance() % GRID,
RAGGED,
"and where the test put it"
);
let region: &'static mut [u8] = unsafe { core::slice::from_raw_parts_mut(rp, N) };
let tiny: &'static mut [u8] = &mut [];
assert_eq!(
init_region(tiny),
Err(FERR_TOO_SMALL),
"a region below one page is refused, and says which"
);
if usable_bytes(rp.expose_provenance(), N) == 0 {
assert_eq!(
init_region(region),
Err(FERR_GEOMETRY),
"a region that cannot hold one segment is refused BEFORE the board"
);
install_region(rp.expose_provenance(), N);
} else {
init_region(region).expect("this geometry's segment fits in N");
}
assert_eq!(free_total(), N, "the whole region starts free");
assert_eq!(extents().len(), 1, "as one extent");
let op = &raw mut OTHER;
let other: &'static mut [u8] =
unsafe { core::slice::from_raw_parts_mut(op.cast::<u8>(), FIXED_PAGE) };
let second = init_region(other);
assert!(second.is_err(), "no second region");
let (a, b, c) = unsafe {
(
alloc(64 * 1024, FIXED_PAGE, true, false).expect("a"),
alloc(128 * 1024, FIXED_PAGE, true, false).expect("b"),
alloc(64 * 1024, FIXED_PAGE, true, false).expect("c"),
)
};
assert_eq!(free_total(), N - 256 * 1024, "three blocks are out");
assert!(!a.is_zero, "recycled memory is never claimed zero");
let base = REGION_BASE.load(Ordering::Relaxed);
for (p, len) in [(a.ptr, 64 * 1024), (b.ptr, 128 * 1024), (c.ptr, 64 * 1024)] {
let off = p.expose_provenance() - base;
assert!(off + len <= N, "block lies inside the region");
}
assert_ne!(a.ptr, b.ptr);
assert_ne!(b.ptr, c.ptr);
for (p, len, tag) in [(a.ptr, 64 * 1024, 0xA5u8), (b.ptr, 128 * 1024, 0x5Au8)] {
unsafe {
core::ptr::write_bytes(p, tag, len);
assert_eq!(*p, tag);
assert_eq!(*p.add(len - 1), tag);
}
}
let holes = extents().len();
unsafe { free(b.ptr, 128 * 1024).expect("free b") };
assert_eq!(free_total(), N - 128 * 1024);
assert_eq!(extents().len(), holes + 1, "an isolated hole");
unsafe {
free(a.ptr, 64 * 1024).expect("free a");
free(c.ptr, 64 * 1024).expect("free c");
}
assert_eq!(free_total(), N, "the whole region is back");
assert_eq!(extents().len(), 1, "coalesced into one extent");
let d = unsafe { alloc(256 * 1024, FIXED_PAGE, true, false).expect("d") };
assert_eq!(free_total(), N - 256 * 1024);
unsafe { free(d.ptr, 256 * 1024).expect("free d") };
assert_eq!(free_total(), N);
assert_eq!(free_total(), N, "the whole region is free before this");
let seg = unsafe { alloc(SEGMENT_SIZE, SEGMENT_SIZE, true, false) };
if SEGMENT_SIZE > N {
assert!(
seg.is_err(),
"a {SEGMENT_SIZE}-byte segment cannot come out of a {N}-byte region"
);
assert_eq!(
free_total(),
N,
"a refused request leaves the list untouched"
);
let base = REGION_BASE.load(Ordering::Relaxed);
if cfg!(ra_aligned_region) {
let boundary = align_up(base, SEGMENT_SIZE);
let straddles = boundary + FIXED_PAGE <= base + N;
let al = unsafe { alloc(FIXED_PAGE, SEGMENT_SIZE, true, false) };
if straddles {
let al = al.expect("the boundary is inside the region, so a page at it fits");
assert_eq!(
al.ptr.expose_provenance(),
boundary,
"served AT the one SEGMENT_SIZE-aligned address the region has"
);
unsafe { free(al.ptr, FIXED_PAGE).expect("free the aligned page") };
} else {
assert!(
al.is_err(),
"no SEGMENT_SIZE-aligned address lies inside this region"
);
}
} else {
let al = unsafe { alloc(FIXED_PAGE, SEGMENT_SIZE, true, false) }
.expect("the region's base is its first segment stride");
assert_eq!(
al.ptr.expose_provenance(),
base,
"served AT the base: stride 0, whatever the address"
);
unsafe { free(al.ptr, FIXED_PAGE).expect("free the aligned page") };
}
assert_eq!(free_total(), N, "and the list is whole again");
} else {
let a = seg.expect("a segment must fit once the geometry allows it");
let base = REGION_BASE.load(Ordering::Relaxed);
if cfg!(ra_aligned_region) {
assert_eq!(
a.ptr.expose_provenance() % SEGMENT_SIZE,
0,
"a segment must be SEGMENT_SIZE-aligned — `segment_of` masks on it"
);
} else {
assert_eq!(
(a.ptr.expose_provenance() - base) % SEGMENT_SIZE,
0,
"a segment sits on a SEGMENT_SIZE stride from the base — `segment_of` masks the offset"
);
assert_eq!(
a.ptr.expose_provenance(),
base,
"the first stride is the base itself"
);
assert_ne!(
a.ptr.expose_provenance() % SEGMENT_SIZE,
0,
"and it is NOT segment-aligned in absolute terms: the region was carved ragged on purpose"
);
}
assert_eq!(free_total(), N.saturating_sub(SEGMENT_SIZE));
unsafe { free(a.ptr, SEGMENT_SIZE).expect("free the segment") };
}
assert_eq!(free_total(), N);
let top = unsafe { alloc(FIXED_PAGE, FIXED_PAGE, true, false).expect("top") };
assert_eq!(
top.ptr.expose_provenance() - REGION_BASE.load(Ordering::Relaxed),
N - FIXED_PAGE,
"a page-aligned request is placed at the top of the region"
);
assert_eq!(
extents(),
vec![(0, N - FIXED_PAGE)],
"and leaves the low end as ONE contiguous extent"
);
unsafe { free(top.ptr, FIXED_PAGE).expect("free top") };
assert_eq!(free_total(), N);
let clean = greedy_segments();
assert_eq!(free_total(), N, "counting segments leaves the region whole");
let hdr = unsafe { alloc(FIXED_PAGE, FIXED_PAGE, true, false).expect("hdr") };
let with_hdr = greedy_segments();
assert_eq!(
with_hdr, clean,
"a page-sized block must not cost a whole segment of reach"
);
unsafe { free(hdr.ptr, FIXED_PAGE).expect("free hdr") };
assert_eq!(free_total(), N, "and the region ends whole");
assert_eq!(free_total(), N, "the region is whole before this");
let seg_count = N / SEGMENT_SIZE;
if seg_count >= 2 {
let size = SEGMENT_SIZE;
let cost = dedicated_segments(size);
if size > LARGEST_SHARED_ALLOC {
assert!(
cost >= 2,
"a SEGMENT_SIZE request cannot fit one segment: the header owns slice 0"
);
}
let served = greedy_dedicated(size);
assert_eq!(free_total(), N, "counting leaves the region whole");
assert!(served >= 1, "a region of {seg_count} segments serves none");
if cost >= 2 {
assert!(
served * size * 2 <= N + SEGMENT_SIZE,
"dedicated blocks cannot use half the region: served {served} x {size} of {N}"
);
}
let seg_taken =
unsafe { alloc(SEGMENT_SIZE, SEGMENT_SIZE, true, false).expect("a segment") };
let after_small = greedy_dedicated(size);
unsafe { free(seg_taken.ptr, SEGMENT_SIZE).expect("free the segment") };
assert_eq!(free_total(), N, "and the region ends whole");
assert!(
after_small <= served,
"taking a segment cannot increase the large-allocation reach"
);
let promised = region_for_allocs(size, served + 1);
assert!(
promised > N,
"region_for_allocs({size}, {}) = {promised} must exceed the {N} that served {served}",
served + 1
);
}
}
fn greedy_dedicated(size: usize) -> usize {
let want = align_up(crate::types::SEGMENT_SLICE_SIZE + size, FIXED_PAGE);
let mut held = Vec::new();
while let Ok(a) = unsafe { alloc(want, SEGMENT_SIZE, true, false) } {
held.push(a.ptr);
}
let n = held.len();
for p in held {
unsafe { free(p, want).expect("free a counted reservation") };
}
n
}
fn greedy_segments() -> usize {
let mut held = Vec::new();
while let Ok(a) = unsafe { alloc(SEGMENT_SIZE, SEGMENT_SIZE, true, false) } {
held.push(a.ptr);
}
let n = held.len();
for p in held {
unsafe { free(p, SEGMENT_SIZE).expect("free a counted segment") };
}
n
}
#[test]
fn good_region_size_strands_nothing() {
use crate::types::SEGMENT_SIZE as SEG;
let budget = 220 * 1024;
let good = good_region_size(budget);
assert!(good <= budget, "a budget is a ceiling");
if budget >= MIN_REGION {
assert_eq!(good, (budget / SEG) * SEG, "whole segments");
assert_eq!(usable_bytes(0, good), good, "every byte is a segment");
assert_eq!(
usable_bytes(0, budget),
usable_bytes(0, good),
"the good size serves as much as the budget did"
);
assert_eq!(
budget - good,
budget % SEG,
"and that is what the budget was stranding"
);
if SEG == 64 * 1024 {
assert_eq!(good, 3 * SEG, "three segments at the default");
assert_eq!(good, 196_608);
assert_eq!(budget - good, 28_672);
}
} else {
assert_eq!(
good, 0,
"no zero-waste region fits a budget below the floor"
);
}
assert_eq!(good_region_size(0), 0);
assert_eq!(good_region_size(MIN_REGION - 1), 0);
assert_eq!(good_region_size(MIN_REGION), MIN_REGION);
let mut b = MIN_REGION;
while b < 40 * SEG {
let g = good_region_size(b);
assert!(g <= b && g >= MIN_REGION);
assert_eq!(g % SEG, 0, "k * SEGMENT_SIZE");
assert_eq!(usable_bytes(0, g), g);
assert!(g + SEG > b, "not the largest: {g} for budget {b}");
b += 4093; }
let need: usize = 192 * 1024;
let k = need.div_ceil(SEG);
assert_eq!(region_for(need), k * SEG);
assert_eq!(usable_bytes(0, region_for(need)), k * SEG);
assert_eq!(region_for(1), SEG, "one byte still costs a segment");
assert_eq!(
region_for(0),
MIN_REGION,
"and so does zero — a region must serve something"
);
assert_eq!(region_for(SEG + 1), 2 * SEG, "a byte over rounds up");
let mut u = 1;
while u < 40 * SEG {
let r = region_for(u);
assert!(
usable_bytes(0, r) >= u,
"region_for({u}) = {r} serves too little"
);
assert!(
usable_bytes(0, r - SEG) < u || r - SEG < MIN_REGION,
"region_for({u}) = {r} is not the smallest"
);
assert_eq!(
good_region_size(r),
r,
"a region_for answer is already a good size"
);
u += 4093;
}
}
#[test]
fn dedicated_segments_names_the_large_allocation_cliff() {
use crate::types::{SEGMENT_SIZE as SEG, SEGMENT_SLICE_SIZE as SLICE};
assert_eq!(dedicated_segments(0), 0);
assert_eq!(dedicated_segments(1), 0);
assert_eq!(dedicated_segments(LARGEST_SHARED_ALLOC), 0);
assert_eq!(LARGEST_SHARED_ALLOC, SEG - SLICE, "the header owns slice 0");
assert_eq!(dedicated_segments(LARGEST_SHARED_ALLOC + 1), 2);
assert_eq!(dedicated_segments(SEG), 2);
assert_eq!(dedicated_segments(2 * SEG), 3);
let mut prev = 0;
let mut size = 0;
while size < 5 * SEG {
let d = dedicated_segments(size);
assert!(d >= prev, "cost cannot fall as the request grows");
if d > 0 {
assert!(d * SEG >= size + SLICE, "must hold header plus payload");
}
prev = d;
size += SLICE / 2 + 1;
}
let three = region_for_allocs(SEG, 3);
assert_eq!(three % SEG, 0, "whole segments");
assert_eq!(good_region_size(three), three, "already a good size");
if dedicated_segments(SEG) == 0 {
assert!(three <= 2 * SEG, "sharing should not need a segment each");
} else {
assert_eq!(
three,
(3 * dedicated_segments(SEG) + 1) * SEG,
"three dedicated runs, plus one segment for everything smaller"
);
}
if SEG == 64 * 1024 {
assert_eq!(dedicated_segments(64 * 1024), 2);
assert_eq!(region_for_allocs(64 * 1024, 3), 448 * 1024);
assert!(
region_for_allocs(64 * 1024, 3) > 256 * 1024,
"the reported 256 KiB region cannot hold three, and now says so"
);
}
}
#[test]
fn a_misaligned_exact_region_is_refused_not_served_short() {
use crate::types::SEGMENT_SIZE as SEG;
let base = 0x3fc8_a1e4usize;
let n = good_region_size(220 * 1024);
if n >= MIN_REGION && SEG == 64 * 1024 {
assert_eq!(n, 196_608);
assert_eq!(usable_bytes(base, n), 131_072, "two segments, not three");
assert!(usable_bytes(base, n) < n);
assert_eq!(usable_bytes(0, n), 196_608, "what the name promised");
if cfg!(ra_aligned_region) {
assert_eq!(
usable_bytes(base + 12, n),
131_072,
"masked: the run-up is 24,080"
);
assert_eq!(
usable_bytes(base, 200_704),
131_072,
"the 2.0.3 shape, same loss"
);
} else {
assert_eq!(
usable_bytes(base + 12, n),
196_608,
"the same region on the grid is the three it says"
);
assert_eq!(
usable_bytes(base, 200_704),
196_608,
"the 2.0.3 shape carries 4 KiB of slack, which absorbs 12 bytes"
);
}
let round = 220 * 1024;
assert_eq!(usable_bytes(base, round), usable_bytes(0, round));
assert_eq!(usable_bytes(base, round), 196_608);
}
let two = 2 * SEG;
assert!(usable_bytes(SEG + 1, two) < usable_bytes(0, two));
assert_eq!(usable_bytes(SEG + 1, two), SEG);
#[cfg(ra_small_profile)]
{
const M: usize = 2 * crate::types::SEGMENT_SIZE;
const SLACK: usize = crate::types::SEGMENT_SIZE + 0x1e4;
static mut MIS: [u8; M + SLACK] = [0; M + SLACK];
let bp = (&raw mut MIS).cast::<u8>().expose_provenance();
let want = (bp & !(SEG - 1)) + SEG + 0x1e4;
let skip = want - bp;
assert!(skip <= SLACK);
let region: &'static mut [u8] = unsafe {
core::slice::from_raw_parts_mut((&raw mut MIS).cast::<u8>().add(skip), M)
};
assert_eq!(
init_region(region),
Err(FERR_MISALIGNED),
"an exact size at a base that costs a segment must be refused, not served short"
);
}
}
#[test]
fn region_type_is_aligned_and_unpadded() {
use crate::types::SEGMENT_SIZE as SEG;
assert_eq!(
core::mem::align_of::<Region<MIN_REGION>>(),
REGION_ALIGN,
"16 bytes: segments stride from the base, so the type owes the linker no gap"
);
assert_eq!(
core::mem::size_of::<Region<MIN_REGION>>(),
MIN_REGION,
"a whole-segment region carries no padding"
);
assert_eq!(Region::<MIN_REGION>::USABLE, SEG);
#[cfg(ra_small_profile)]
{
#[cfg(not(ra_aligned_region))]
let r: &'static Region<MIN_REGION> = {
static R: Region<MIN_REGION> = Region::new();
&R
};
#[cfg(ra_aligned_region)]
let r: &'static Region<MIN_REGION> =
Box::leak(unsafe { Box::<Region<MIN_REGION>>::new_zeroed().assume_init() });
assert_eq!(r.usable(), Region::<MIN_REGION>::USABLE);
assert_eq!(r.len(), MIN_REGION);
assert!(!r.is_empty());
}
}
#[test]
fn the_direct_route_boundary_moves_with_pointer_width() {
use crate::types::{SMALL_OBJ_SIZE_MAX, SMALL_SIZE_MAX, SMALL_WSIZE_MAX};
assert_eq!(
SMALL_SIZE_MAX,
SMALL_WSIZE_MAX * core::mem::size_of::<usize>()
);
assert!(shape_of(SMALL_SIZE_MAX).direct_route);
assert!(!shape_of(SMALL_SIZE_MAX + 1).direct_route);
if core::mem::size_of::<usize>() == 8 {
assert_eq!(SMALL_SIZE_MAX, 1024);
} else if core::mem::size_of::<usize>() == 4 {
assert_eq!(SMALL_SIZE_MAX, 512);
}
assert_eq!(SMALL_OBJ_SIZE_MAX, crate::types::SEGMENT_SLICE_SIZE / 8);
let coincide = SMALL_SIZE_MAX == SMALL_OBJ_SIZE_MAX;
assert_eq!(
coincide,
SMALL_WSIZE_MAX * core::mem::size_of::<usize>() == crate::types::SEGMENT_SLICE_SIZE / 8,
"the two boundaries coincide exactly when the arithmetic says so"
);
assert!(shape_of(16).page_bytes <= shape_of(SMALL_OBJ_SIZE_MAX).page_bytes);
assert!(
shape_of(SMALL_OBJ_SIZE_MAX + 1).page_bytes > shape_of(SMALL_OBJ_SIZE_MAX).page_bytes
);
assert_eq!(shape_of(16).dedicated_segments, 0);
assert!(shape_of(LARGEST_SHARED_ALLOC + 1).dedicated_segments >= 1);
}
#[test]
fn usable_bytes_answers_the_question_a_firmware_asks() {
let seg = SEGMENT_SIZE;
assert_eq!(
usable_bytes(0, MIN_REGION),
seg,
"MIN_REGION buys a segment"
);
assert_eq!(
usable_bytes(0, MIN_REGION - 1),
0,
"one byte short buys none"
);
assert_eq!(usable_bytes(0, seg), seg, "a bare segment is a segment");
assert_eq!(
usable_bytes(FIXED_PAGE, MIN_REGION),
if cfg!(ra_aligned_region) { 0 } else { seg },
"a base off the segment grid serves the segment, because strides start at the base \
(masked, the run-up eats it)"
);
assert_eq!(usable_bytes(REGION_ALIGN, MIN_REGION), seg);
assert_eq!(usable_bytes(3 * seg + 5 * REGION_ALIGN, MIN_REGION), seg);
assert_eq!(
usable_bytes(REGION_ALIGN + 1, MIN_REGION),
0,
"a base off the grid eats the segment"
);
assert_eq!(
usable_bytes(REGION_ALIGN + 1, MIN_REGION + REGION_ALIGN),
seg,
"sixteen bytes of slack absorb it"
);
let three_and_a_bit = 3 * seg + seg / 2;
assert_eq!(
usable_bytes(0, three_and_a_bit),
3 * seg,
"a ragged region yields whole segments and strands the remainder"
);
let stranded = three_and_a_bit - usable_bytes(0, three_and_a_bit);
assert_eq!(
stranded,
seg / 2,
"and the strand is exactly the ragged part"
);
}
#[cfg(ra_single_threaded)]
#[test]
#[should_panic(expected = "re-entered")]
fn a_reentrant_acquire_is_diagnosed_not_hung() {
static LOCK2: AtomicBool = AtomicBool::new(false);
let _outer = Guard::acquire(&LOCK2);
let _inner = Guard::acquire(&LOCK2);
}
#[test]
fn no_mmu_semantics_are_explicit() {
let cfg = mem_init();
assert_eq!(cfg.page_size, FIXED_PAGE);
assert_eq!(cfg.large_page_size, 0, "no large pages without an MMU");
assert!(!cfg.has_overcommit, "nothing to overcommit");
assert!(cfg.has_partial_free, "any extent can be returned");
assert_ne!(thread_id(), 0, "zero is the abandoned-segment sentinel");
assert_eq!(numa_node_count(), 1);
assert!(clock_now() < clock_now());
let p = unsafe { protect(core::ptr::null_mut(), FIXED_PAGE, true) };
assert!(
p.is_err(),
"a guard page that cannot trap must not report success"
);
}
}