use crate::allocator::{bin_class, bin_index};
use crate::*;
struct TestConfig;
impl Config for TestConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 65536;
const HEAP_BASE: u64 = 0x1_0000;
const HEAP_SIZE: u64 = 0x10_0000;
}
const _: () = assert_config_valid::<TestConfig>();
#[test]
fn const_heap_accessors_read_compile_time_values() {
assert_eq!(const_heap_base::<TestConfig>(), 0x1_0000);
assert_eq!(const_heap_size::<TestConfig>(), 0x10_0000);
assert_eq!(TestConfig::heap_base(), 0x1_0000);
assert_eq!(TestConfig::heap_size(), 0x10_0000);
}
#[test]
fn slice_null_and_bounds() {
assert!(Slice::NULL.is_null());
assert!(SliceView::NULL.is_null());
let s = unsafe { SliceView::new(0x1000, 0x100) };
assert!(!s.is_null());
assert!(!s.is_empty());
assert_eq!(s.end(), 0x1100);
assert_eq!(s.range(), 0x1000..0x1100);
assert!(s.contains(0x1000));
assert!(s.contains(0x10FF));
assert!(!s.contains(0x1100));
assert!(s.is_aligned_to(0x1000) && !s.is_aligned_to(0x2000));
let inner = s.subslice(0x40, 0x40).expect("in bounds");
assert_eq!((inner.ptr(), inner.len()), (0x1040, 0x40));
assert!(s.covers(&inner) && s.overlaps(&inner));
assert!(s.subslice(0x100, 1).is_none()); let tail = unsafe { s.subslice_unchecked(0x80, 0x80) };
assert!(!inner.overlaps(&tail));
let (head, rest) = s.split_at(0x80).expect("in bounds");
assert_eq!(head.len(), 0x80);
assert_eq!(rest.ptr(), 0x1080);
assert!(s.split_at(0x101).is_none());
let mut v = [
unsafe { SliceView::new(30, 1) },
unsafe { SliceView::new(10, 5) },
unsafe { SliceView::new(10, 1) },
];
v.sort();
assert_eq!(
v,
[
unsafe { SliceView::new(10, 1) },
unsafe { SliceView::new(10, 5) },
unsafe { SliceView::new(30, 1) },
]
);
assert_eq!(std::format!("{s:?}"), "SliceView { ptr: 0x1000, len: 256 }");
}
#[test]
fn slice_view_reads_and_writes_memory() {
let mut buf = [0u8; 64];
let base = buf.as_mut_ptr() as u64;
let s = unsafe { SliceView::new(base, 64) };
assert_eq!(s.as_ptr() as u64, base);
let mid = s.subslice(16, 32).unwrap();
unsafe {
for (i, b) in mid.as_bytes_mut().iter_mut().enumerate() {
*b = i as u8;
}
}
unsafe {
let bytes = mid.as_bytes();
assert_eq!(bytes.len(), 32);
assert_eq!(bytes[5], 5);
}
assert_eq!(buf[16 + 5], 5);
}
#[test]
fn slice_owns_and_converts_to_view() {
let owner = unsafe { Slice::new(0x2000, 0x80) };
assert_eq!(owner.end(), 0x2080);
assert!(owner.contains(0x2000));
let v = owner.view();
assert_eq!(v.ptr(), owner.ptr());
assert_eq!(v.len(), owner.len());
let back = owner.into_view(); let owner2 = unsafe { back.to_slice() };
assert_eq!(owner2.len(), 0x80);
let _: SliceView<'static> = SliceView::from(owner2);
}
#[test]
fn core_atomics_round_trip() {
let cell = core::sync::atomic::AtomicU64::new(0);
let addr = &cell as *const _ as u64;
unsafe {
CoreAtomics::atomic_store(addr, 10);
assert_eq!(CoreAtomics::atomic_load(addr), 10);
assert_eq!(CoreAtomics::atomic_add(addr, 5), 10);
assert_eq!(CoreAtomics::atomic_load(addr), 15);
assert_eq!(CoreAtomics::atomic_cas(addr, 15, 20), 15);
assert_eq!(CoreAtomics::atomic_load(addr), 20);
assert_eq!(CoreAtomics::atomic_cas(addr, 99, 0), 20); assert_eq!(CoreAtomics::atomic_swap(addr, 7), 20);
assert_eq!(CoreAtomics::atomic_dec(addr), 7);
assert_eq!(CoreAtomics::atomic_load(addr), 6);
CoreAtomics::atomic_store(addr, 0b1010);
assert_eq!(CoreAtomics::atomic_or(addr, 0b0100), 0b1010);
assert_eq!(CoreAtomics::atomic_load(addr), 0b1110);
assert_eq!(CoreAtomics::atomic_and(addr, 0b1100), 0b1110);
assert_eq!(CoreAtomics::atomic_load(addr), 0b1100);
loop {
let (read, ok) = CoreAtomics::atomic_cas_weak(addr, 0b1100, 42);
assert_eq!(read, 0b1100);
if ok {
break;
}
}
assert_eq!(CoreAtomics::atomic_load(addr), 42);
let (read, ok) = CoreAtomics::atomic_cas_weak(addr, 999, 0);
assert!(!ok);
assert_eq!(read, 42);
}
}
#[test]
fn bin_counts_are_statically_computed() {
assert_eq!(TestConfig::NUM_LINEAR, 14);
assert_eq!(TestConfig::NUM_EXP, 17);
assert_eq!(TestConfig::NUM_BINS, 32);
}
#[test]
fn bin_classes_are_ordered_and_aligned() {
let fixed = TestConfig::NUM_BINS - 1;
let mut prev = 0;
for k in 0..fixed {
let c = bin_class::<TestConfig>(k);
assert!(c > prev, "bin {k} class {c} not increasing from {prev}");
assert_eq!(c % TestConfig::MIN_ALIGN, 0, "bin {k} class {c} misaligned");
prev = c;
}
assert_eq!(bin_class::<TestConfig>(0), 32);
assert_eq!(bin_class::<TestConfig>(13), 240);
assert_eq!(bin_class::<TestConfig>(14), 256);
assert_eq!(bin_class::<TestConfig>(15), 384);
assert_eq!(bin_class::<TestConfig>(fixed - 1), 65536);
assert_eq!(bin_class::<TestConfig>(fixed), u64::MAX); }
#[test]
fn bin_index_round_trips_every_class() {
let fixed = TestConfig::NUM_BINS - 1;
for k in 0..fixed {
let c = bin_class::<TestConfig>(k);
assert_eq!(
bin_index::<TestConfig>(c),
k,
"class {c} did not map back to bin {k}"
);
}
}
#[test]
fn bin_index_always_fits() {
for s in [
1u64, 15, 16, 17, 100, 240, 241, 255, 256, 257, 384, 385, 512, 4096, 65535, 65536,
] {
let k = bin_index::<TestConfig>(s);
assert!(
k < TestConfig::NUM_BINS - 1,
"size {s} unexpectedly oversized"
);
assert!(
bin_class::<TestConfig>(k) >= s,
"bin {k} class too small for {s}"
);
}
assert_eq!(bin_index::<TestConfig>(65537), TestConfig::NUM_BINS - 1);
assert_eq!(bin_index::<TestConfig>(1 << 30), TestConfig::NUM_BINS - 1);
}
#[test]
fn largest_carvable_matches_brute_force() {
type C = TestConfig;
fn align_up(x: u64, a: u64) -> u64 {
(x + (a - 1)) & !(a - 1)
}
fn class_align(v: u64) -> u64 {
if v < C::EXP_FLOOR {
C::MIN_ALIGN
} else {
let a = 1u64 << (v.ilog2() - 1);
if a < C::MIN_ALIGN { C::MIN_ALIGN } else { a }
}
}
fn reference(end: u64, len: u64) -> u64 {
let mut cap = len;
if len > C::EXP_CEIL {
let size = end - align_up(end - len, C::EXP_CEIL);
if size > C::EXP_CEIL {
return size;
}
cap = C::EXP_CEIL;
}
let mut best = 0;
let fixed = C::NUM_BINS - 1;
let mut bin = 0;
while bin < fixed {
let c = bin_class::<C>(bin);
if c <= cap && end % class_align(c) == 0 && c > best {
best = c;
}
bin += 1;
}
best
}
for ez in 4..21u32 {
for m in 0..3u64 {
let end = ((2 * m + 1) + (1u64 << 20)) << ez;
for &len in &[
1u64, 16, 100, 240, 255, 256, 300, 500, 768, 1000, 2048, 3000, 4096, 6144, 60000,
65536, 70000, 200000,
] {
let (size, bin) = CadAlloc::<C>::largest_carvable(end, len);
let expected = reference(end, len);
assert_eq!(size, expected, "end={end:#x} len={len}: size mismatch");
if size == 0 {
continue;
}
if bin == C::NUM_BINS - 1 {
assert!(size > C::EXP_CEIL, "oversized bin holds a small block");
assert_eq!((end - size) % C::EXP_CEIL, 0, "oversized misaligned");
} else {
assert_eq!(bin_class::<C>(bin), size, "bin/size disagree");
assert_eq!(end % class_align(size), 0, "carved block misaligned");
}
}
}
}
}
const MAGIC_LE: u64 = u64::from_le_bytes(*b"CADALLOC");
const HEAP_N: usize = 1 << 16;
#[repr(C, align(64))]
struct Heap([u8; HEAP_N]);
static mut HEAP: Heap = Heap([0; HEAP_N]);
fn heap_base_addr() -> u64 {
&raw const HEAP as u64
}
struct HeapConfig;
impl Config for HeapConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
fn heap_base() -> u64 {
heap_base_addr()
}
fn heap_size() -> u64 {
HEAP_N as u64
}
}
struct MismatchConfig;
impl Config for MismatchConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 8192; fn heap_base() -> u64 {
heap_base_addr()
}
fn heap_size() -> u64 {
HEAP_N as u64
}
}
#[test]
fn allocator_alloc_free_reuse() {
let a = CadAlloc::<HeapConfig>::new();
assert_eq!(a.verify(), Err(VerifyError::BadMagic));
a.init().expect("init");
assert_eq!(a.verify(), Ok(()));
assert_eq!(CadAlloc::<HeapConfig>::magic(), MAGIC_LE);
assert_eq!(
CadAlloc::<MismatchConfig>::new().verify(),
Err(VerifyError::ConfigMismatch)
);
let s1 = a.alloc(100);
assert!(!s1.is_null());
assert_eq!(s1.ptr % 16, 0, "payload must be MIN_ALIGN-aligned");
assert!(s1.len >= 100, "capacity {} < requested 100", s1.len);
let s2 = a.alloc(100);
assert!(!s2.is_null());
assert_ne!(s1.ptr, s2.ptr);
assert!(
s2.ptr >= s1.ptr + s1.len || s1.ptr >= s2.ptr + s2.len,
"blocks overlap"
);
let p1 = s1.ptr;
a.free(s1);
let s3 = a.alloc(100);
assert_eq!(s3.ptr, p1, "freed block should be reused");
a.free(s2);
a.free(s3);
let big = a.alloc(5000);
assert!(!big.is_null());
assert!(big.len >= 5000);
let bp = big.ptr;
a.free(big);
let big2 = a.alloc(5000);
assert_eq!(big2.ptr, bp, "oversized block should be reused");
a.free(big2);
}
#[test]
fn init_rejects_bad_heap() {
struct Misaligned;
impl Config for Misaligned {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
fn heap_base() -> u64 {
heap_base_addr() + 8 }
fn heap_size() -> u64 {
HEAP_N as u64
}
}
assert_eq!(
CadAlloc::<Misaligned>::new().init(),
Err(InitError::MisalignedHeap)
);
struct Tiny;
impl Config for Tiny {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
fn heap_base() -> u64 {
heap_base_addr()
}
fn heap_size() -> u64 {
16 }
}
assert_eq!(CadAlloc::<Tiny>::new().init(), Err(InitError::HeapTooSmall));
}
#[repr(C, align(64))]
struct FfiHeap([u8; HEAP_N]);
static mut FFI_HEAP: FfiHeap = FfiHeap([0; HEAP_N]);
fn ffi_heap_base() -> u64 {
&raw const FFI_HEAP as u64
}
struct FfiConfig;
impl Config for FfiConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
fn heap_base() -> u64 {
ffi_heap_base()
}
fn heap_size() -> u64 {
HEAP_N as u64
}
}
crate::export_c_api! {
config: FfiConfig,
init: cadtest_init,
alloc: cadtest_alloc,
realloc: cadtest_realloc,
free: cadtest_free,
verify: cadtest_verify,
}
#[test]
fn ffi_shims_round_trip() {
assert_eq!(cadtest_verify(), 1);
assert_eq!(cadtest_init(), 0);
assert_eq!(cadtest_verify(), 0);
let s = cadtest_alloc(100);
assert!(!s.is_null());
assert!(s.len() >= 100);
let sp = s.ptr(); cadtest_free(s);
let s2 = cadtest_alloc(100);
assert_eq!(s2.ptr(), sp);
let s3 = cadtest_realloc(s2, 2000);
assert!(!s3.is_null());
assert!(s3.len >= 2000);
cadtest_free(s3);
let s4 = cadtest_realloc(Slice::NULL, 64);
assert!(!s4.is_null());
cadtest_free(s4);
}
#[repr(C, align(64))]
struct DfHeap([u8; HEAP_N]);
static mut DF_HEAP: DfHeap = DfHeap([0; HEAP_N]);
struct DfConfig;
impl Config for DfConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
fn heap_base() -> u64 {
&raw const DF_HEAP as u64
}
fn heap_size() -> u64 {
HEAP_N as u64
}
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "double free")]
fn double_free_is_detected() {
let a = CadAlloc::<DfConfig>::new();
a.init().expect("init");
let s = a.alloc(100);
assert!(!s.is_null());
let dup = unsafe { Slice::new(s.ptr(), s.len()) };
a.free(s);
a.free(dup); }
#[repr(C, align(64))]
struct ReallocHeap([u8; HEAP_N]);
static mut REALLOC_HEAP: ReallocHeap = ReallocHeap([0; HEAP_N]);
fn realloc_heap_base() -> u64 {
&raw const REALLOC_HEAP as u64
}
struct ReallocConfig;
impl Config for ReallocConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
fn heap_base() -> u64 {
realloc_heap_base()
}
fn heap_size() -> u64 {
HEAP_N as u64
}
}
#[test]
fn realloc_grows_shrinks_relocates() {
let a = CadAlloc::<ReallocConfig>::new();
a.init().expect("init");
let n = a.realloc(Slice::NULL, 50);
assert!(!n.is_null());
a.free(n);
let s = a.alloc(64);
assert!(!s.is_null());
unsafe {
for i in 0..64u64 {
(s.ptr as *mut u8).add(i as usize).write(i as u8);
}
}
let g = a.realloc(s, 2000);
assert!(!g.is_null());
assert!(g.len >= 2000);
unsafe {
for i in 0..64u64 {
assert_eq!((g.ptr as *const u8).add(i as usize).read(), i as u8);
}
}
a.free(g);
let f = a.alloc(2000);
let (fp, cap) = (f.ptr(), f.len());
let t = a.realloc(f, 100);
assert_eq!(t.ptr(), fp, "fixed shrink should not move");
assert_eq!(t.len(), cap, "fixed shrink keeps the whole block");
a.free(t);
let big = a.alloc(12000);
let (bp, bl) = (big.ptr(), big.len());
assert!(bl >= 12000);
let sh = a.realloc(big, 5000);
assert_eq!(sh.ptr(), bp, "oversized shrink stays in place");
assert!(sh.len() >= 5000 && sh.len() < bl, "block actually shrank");
let other = a.alloc(3000);
assert!(!other.is_null());
assert!(
!overlap(sh.view(), other.view()),
"new allocation overlaps the retained block"
);
a.free(other);
a.free(sh);
}
#[repr(C, align(64))]
struct CarveHeap([u8; HEAP_N]);
static mut CARVE_HEAP: CarveHeap = CarveHeap([0; HEAP_N]);
fn carve_heap_base() -> u64 {
&raw const CARVE_HEAP as u64
}
struct CarveConfig;
impl Config for CarveConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
const SPLIT_MIN: u64 = 256; const CARVE_MAX: u64 = 8; fn heap_base() -> u64 {
carve_heap_base()
}
fn heap_size() -> u64 {
HEAP_N as u64
}
}
const _: () = assert_config_valid::<CarveConfig>();
fn overlap(a: SliceView<'_>, b: SliceView<'_>) -> bool {
a.overlaps(&b)
}
const ALIGN_HEAP_N: usize = 1 << 20;
#[repr(C, align(64))]
struct AlignHeap([u8; ALIGN_HEAP_N]);
static mut ALIGN_HEAP: AlignHeap = AlignHeap([0; ALIGN_HEAP_N]);
fn align_heap_base() -> u64 {
&raw const ALIGN_HEAP as u64
}
struct AlignConfig;
impl Config for AlignConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 65536;
fn heap_base() -> u64 {
align_heap_base()
}
fn heap_size() -> u64 {
ALIGN_HEAP_N as u64
}
}
#[test]
fn bump_aligns_exponential_blocks() {
let a = CadAlloc::<AlignConfig>::new();
a.init().expect("init");
for &sz in &[300u64, 500, 2000, 5000, 9000] {
let s = a.alloc(sz);
assert!(!s.is_null());
let header = s.ptr - 16; let class = s.len + 16; assert!(class >= AlignConfig::EXP_FLOOR, "not exponential: {class}");
let align = 1u64 << (class.ilog2() - 1);
assert_eq!(
header % align,
0,
"class {class} header {header:#x} not {align}-aligned"
);
a.free(s);
}
for &sz in &[70_000u64, 100_000, 200_000] {
let s = a.alloc(sz);
assert!(!s.is_null());
assert!(s.len + 16 > AlignConfig::EXP_CEIL, "not oversized");
assert_eq!(
(s.ptr - 16) % AlignConfig::EXP_CEIL,
0,
"oversized header {:#x} not EXP_CEIL-aligned",
s.ptr - 16
);
a.free(s);
}
}
#[test]
fn fixed_range_carve_is_non_overlapping() {
let a = CadAlloc::<CarveConfig>::new();
a.init().expect("init");
let big = a.alloc(4080);
assert!(!big.is_null());
let bp = big.ptr();
let small = a.realloc(big, 100);
assert_eq!(small.ptr(), bp, "shrink stays in place");
assert!(small.len() >= 100 && small.len() < 4080, "block shrank");
let heap_lo = carve_heap_base();
let heap_hi = heap_lo + HEAP_N as u64;
let mut live = [Slice::NULL; 25];
live[0] = small;
for k in 1..live.len() {
let sz = 16 + (k as u64 % 6) * 130;
let s = a.alloc(sz);
assert!(!s.is_null(), "alloc {k} failed");
assert_eq!(s.ptr() % 16, 0, "payload misaligned");
assert!(s.ptr() >= heap_lo && s.end() <= heap_hi, "out of heap");
for prev in &live[..k] {
assert!(
!overlap(s.view(), prev.view()),
"allocation {k} overlaps an earlier one"
);
}
live[k] = s;
}
for s in live {
a.free(s);
}
}
#[repr(C, align(65536))]
struct ShrinkHeap([u8; 1 << 20]);
static mut SHRINK_HEAP: ShrinkHeap = ShrinkHeap([0; 1 << 20]);
struct ShrinkConfig;
impl Config for ShrinkConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 8192;
const SPLIT_MIN: u64 = 256; const CARVE_MAX: u64 = 2; fn heap_base() -> u64 {
&raw const SHRINK_HEAP as u64
}
fn heap_size() -> u64 {
(1 << 20) as u64
}
}
const _: () = assert_config_valid::<ShrinkConfig>();
#[test]
fn realloc_shrink_retains_class_exact_aligned_block() {
type C = ShrinkConfig;
fn class_align(size: u64) -> u64 {
if size > C::EXP_CEIL {
C::EXP_CEIL
} else if size < C::EXP_FLOOR {
C::MIN_ALIGN
} else {
(1u64 << (size.ilog2() - 1)).max(C::MIN_ALIGN)
}
}
fn is_class_exact(size: u64) -> bool {
size > C::EXP_CEIL || bin_class::<C>(bin_index::<C>(size)) == size
}
let a = CadAlloc::<C>::new();
a.init().expect("init");
for &sz in &[9_000u64, 10_000, 12_016, 16_000, 20_000, 30_000, 50_000] {
let big = a.alloc(sz);
assert!(!big.is_null(), "alloc {sz} failed");
let bp = big.ptr();
let s = a.realloc(big, 200);
assert_eq!(s.ptr(), bp, "oversized shrink should stay in place");
let block = s.ptr() - C::MIN_ALIGN;
let class = s.len() + C::MIN_ALIGN; assert!(
is_class_exact(class),
"retained size {class} (from {sz}) is not class-exact"
);
assert_eq!(
block % class_align(class),
0,
"retained block {block:#x} (size {class}) not aligned to its class"
);
let other = a.alloc(200);
assert!(!other.is_null());
assert!(
other.ptr >= s.ptr + s.len || s.ptr >= other.ptr + other.len,
"new allocation overlaps the retained block"
);
a.free(other);
a.free(s);
}
assert_eq!(a.verify(), Ok(()));
}
#[cfg(feature = "alloc")]
mod global_alloc {
use super::*;
use core::alloc::{GlobalAlloc, Layout};
const GA_HEAP_N: usize = 1 << 16;
#[repr(C, align(64))]
struct GaHeap([u8; GA_HEAP_N]);
static mut GA_HEAP: GaHeap = GaHeap([0; GA_HEAP_N]);
struct GaConfig;
impl Config for GaConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 4096;
fn heap_base() -> u64 {
&raw const GA_HEAP as u64
}
fn heap_size() -> u64 {
GA_HEAP_N as u64
}
}
#[test]
fn global_alloc_impl_round_trips() {
let a = CadAlloc::<GaConfig>::new();
a.init().expect("init");
let layout = Layout::from_size_align(100, 8).unwrap();
let over = Layout::from_size_align(64, 256).unwrap();
assert!(unsafe { GlobalAlloc::alloc(&a, over) }.is_null());
let d = unsafe { GlobalAlloc::alloc(&a, layout) };
assert!(!d.is_null());
unsafe { core::ptr::write_bytes(d, 0xFF, 100) };
unsafe { GlobalAlloc::dealloc(&a, d, layout) };
let z = unsafe { GlobalAlloc::alloc_zeroed(&a, layout) };
assert_eq!(z, d, "freed block of the same class should be reused");
for i in 0..100 {
assert_eq!(unsafe { *z.add(i) }, 0, "alloc_zeroed left byte {i} dirty");
}
unsafe { GlobalAlloc::dealloc(&a, z, layout) };
let p = unsafe { GlobalAlloc::alloc(&a, layout) };
assert!(!p.is_null());
assert_eq!(p as u64 % 16, 0, "not MIN_ALIGN-aligned");
unsafe { core::ptr::write_bytes(p, 0xAB, 100) };
let p2 = unsafe { GlobalAlloc::realloc(&a, p, layout, 5000) };
assert!(!p2.is_null());
for i in 0..100 {
assert_eq!(unsafe { *p2.add(i) }, 0xAB, "realloc lost byte {i}");
}
unsafe { GlobalAlloc::dealloc(&a, p2, Layout::from_size_align(5000, 8).unwrap()) };
assert_eq!(a.verify(), Ok(()));
}
}
#[cfg(not(loom))]
mod stress {
use super::*;
use std::sync::atomic::{AtomicU64, Ordering};
use std::vec::Vec;
const STRESS_HEAP_N: usize = 4 << 20;
#[repr(C, align(64))]
struct StressHeap([u8; STRESS_HEAP_N]);
static mut STRESS_HEAP: StressHeap = StressHeap([0; STRESS_HEAP_N]);
fn stress_base() -> u64 {
&raw const STRESS_HEAP as u64
}
struct StressConfig;
impl Config for StressConfig {
type Atomics = CoreAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 8192; fn heap_base() -> u64 {
stress_base()
}
fn heap_size() -> u64 {
STRESS_HEAP_N as u64
}
}
static NEXT_TOKEN: AtomicU64 = AtomicU64::new(1);
fn fill(s: SliceView<'_>, token: u64) {
let words = (s.len() / 8) as usize;
let p = s.as_mut_ptr() as *mut u64;
for i in 0..words {
unsafe { p.add(i).write_volatile(token) };
}
}
fn check_prefix(s: SliceView<'_>, token: u64, words: usize) {
let p = s.as_ptr() as *const u64;
for i in 0..words {
let v = unsafe { p.add(i).read_volatile() };
assert_eq!(v, token, "corruption at word {i} of {:#x}", s.ptr());
}
}
fn check(s: SliceView<'_>, token: u64) {
check_prefix(s, token, (s.len() / 8) as usize);
}
#[test]
fn concurrent_alloc_free_realloc_no_corruption() {
let a = CadAlloc::<StressConfig>::new();
a.init().expect("init");
assert_eq!(a.verify(), Ok(()));
const THREADS: usize = 8;
const OPS: usize = 6000;
let mut handles = Vec::new();
for t in 0..THREADS {
handles.push(std::thread::spawn(move || {
let a = CadAlloc::<StressConfig>::new();
let mut rng =
0x9E37_79B9_7F4A_7C15u64 ^ (t as u64 + 1).wrapping_mul(0xD1B5_4A32_D192_ED03);
let mut next = move || {
rng ^= rng << 13;
rng ^= rng >> 7;
rng ^= rng << 17;
rng
};
let mut live: Vec<(Slice, u64)> = Vec::new();
for _ in 0..OPS {
let roll = next() % 100;
if roll < 45 || live.is_empty() {
let size = 8 + next() % 12_000;
let s = a.alloc(size);
if !s.is_null() {
assert_eq!(s.ptr() % 16, 0, "payload misaligned");
assert!(s.len() >= size);
let token = NEXT_TOKEN.fetch_add(1, Ordering::Relaxed);
fill(s.view(), token);
live.push((s, token));
}
} else if roll < 80 {
let i = (next() as usize) % live.len();
let (s, token) = live.swap_remove(i);
check(s.view(), token);
a.free(s);
} else {
let i = (next() as usize) % live.len();
let (old, token) = live.swap_remove(i);
check(old.view(), token);
let (op, ol) = (old.ptr(), old.len());
let new_size = 8 + next() % 12_000;
let g = a.realloc(old, new_size);
if g.is_null() {
let restored = unsafe { Slice::new(op, ol) };
check(restored.view(), token);
live.push((restored, token));
} else {
let kept = core::cmp::min(ol, g.len());
check_prefix(g.view(), token, (kept / 8) as usize);
let token = NEXT_TOKEN.fetch_add(1, Ordering::Relaxed);
fill(g.view(), token);
live.push((g, token));
}
}
}
for (s, token) in live {
check(s.view(), token);
a.free(s);
}
}));
}
for h in handles {
h.join()
.expect("a stress thread panicked (corruption detected)");
}
assert_eq!(a.verify(), Ok(()));
let s = a.alloc(64);
assert!(!s.is_null(), "heap unusable after stress");
a.free(s);
}
}
#[cfg(loom)]
mod loom_stack {
use crate::allocator::CadAlloc;
use crate::atomic::Atomics;
use crate::config::Config;
use loom::sync::Arc;
use loom::sync::atomic::{AtomicU64, Ordering::SeqCst};
use std::cell::Cell;
use std::vec::Vec;
const BASE: u64 = 0x1_0000;
const CELLS: usize = 32;
struct LoomHeap {
words: Vec<AtomicU64>,
}
impl LoomHeap {
fn new() -> Self {
let mut words = Vec::with_capacity(CELLS);
for _ in 0..CELLS {
words.push(AtomicU64::new(0));
}
Self { words }
}
fn at(&self, addr: u64) -> &AtomicU64 {
&self.words[((addr - BASE) / 8) as usize]
}
}
std::thread_local! {
static HEAP: Cell<*const LoomHeap> = const { Cell::new(core::ptr::null()) };
}
fn set_heap(h: &Arc<LoomHeap>) {
HEAP.with(|c| c.set(&**h as *const LoomHeap));
}
fn with_heap<R>(f: impl FnOnce(&LoomHeap) -> R) -> R {
HEAP.with(|c| {
let h = unsafe { &*c.get() };
f(h)
})
}
struct LoomAtomics;
impl Atomics for LoomAtomics {
unsafe fn atomic_load(addr: u64) -> u64 {
with_heap(|h| h.at(addr).load(SeqCst))
}
unsafe fn atomic_store(addr: u64, val: u64) {
with_heap(|h| h.at(addr).store(val, SeqCst));
}
unsafe fn atomic_cas(addr: u64, current: u64, new: u64) -> u64 {
with_heap(
|h| match h.at(addr).compare_exchange(current, new, SeqCst, SeqCst) {
Ok(p) | Err(p) => p,
},
)
}
unsafe fn atomic_cas_weak(addr: u64, current: u64, new: u64) -> (u64, bool) {
with_heap(|h| {
match h
.at(addr)
.compare_exchange_weak(current, new, SeqCst, SeqCst)
{
Ok(p) => (p, true),
Err(p) => (p, false),
}
})
}
}
struct LoomConfig;
impl Config for LoomConfig {
type Atomics = LoomAtomics;
const MIN_ALIGN: u64 = 16;
const LNR_FLOOR: u64 = 32;
const EXP_FLOOR: u64 = 256;
const EXP_CEIL: u64 = 65536;
const HEAP_BASE: u64 = BASE;
const HEAP_SIZE: u64 = (CELLS as u64) * 8;
}
#[test]
fn treiber_stack_push_pop_conserves_blocks() {
loom::model(|| {
let heap = Arc::new(LoomHeap::new());
set_heap(&heap);
const A: u64 = BASE + 64;
const B: u64 = BASE + 96;
let h1 = heap.clone();
let t1 = loom::thread::spawn(move || {
set_heap(&h1);
let a = CadAlloc::<LoomConfig>::new();
a.push_fixed(0, A);
a.pop_fixed(0)
});
let h2 = heap.clone();
let t2 = loom::thread::spawn(move || {
set_heap(&h2);
let a = CadAlloc::<LoomConfig>::new();
a.push_fixed(0, B);
a.pop_fixed(0)
});
let r1 = t1.join().unwrap();
let r2 = t2.join().unwrap();
let a = CadAlloc::<LoomConfig>::new();
assert_eq!(a.pop_fixed(0), 0, "stack not empty after both pops");
assert!(r1 != 0 && r2 != 0, "a pop lost its block: {r1:#x}, {r2:#x}");
assert_ne!(r1, r2, "the same block was popped twice");
let mut got = [r1, r2];
got.sort_unstable();
assert_eq!(got, [A, B], "popped blocks are not {{A, B}}");
});
}
}