use crate::atomic::Atomics;
use crate::config::Config;
use crate::slice::Slice;
use core::hint::spin_loop;
use core::marker::PhantomData;
const FLAG_MASK: u64 = 0xF;
const FREE: u64 = 1;
const USED: u64 = 0;
#[inline(always)]
const fn pack(size: u64, flag: u64) -> u64 {
size | (flag & FLAG_MASK)
}
#[inline(always)]
const fn header_size(header: u64) -> u64 {
header & !FLAG_MASK
}
#[inline(always)]
const fn header_is_free(header: u64) -> bool {
(header & FLAG_MASK) == FREE
}
#[inline(always)]
const fn align_up(x: u64, align: u64) -> u64 {
(x + (align - 1)) & !(align - 1)
}
pub(crate) const MAGIC: u64 = u64::from_le_bytes(*b"CADALLOC");
const META_BYTES: u64 = 16;
#[inline(always)]
const fn splitmix64(mut z: u64) -> u64 {
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
#[inline]
pub(crate) const fn config_fingerprint<C: Config>() -> u64 {
let packed = (C::MIN_ALIGN.ilog2() as u64)
| ((C::LNR_FLOOR.ilog2() as u64) << 6)
| ((C::EXP_FLOOR.ilog2() as u64) << 12)
| ((C::EXP_CEIL.ilog2() as u64) << 18)
| ((C::SPLIT_MIN.ilog2() as u64) << 24);
splitmix64(packed ^ C::CARVE_MAX.wrapping_mul(0x9E37_79B9_7F4A_7C15))
}
#[inline]
pub(crate) const fn bin_class<C: Config>(bin: u64) -> u64 {
if bin < C::NUM_LINEAR {
C::LNR_FLOOR + bin * C::MIN_ALIGN
} else if bin < C::NUM_LINEAR + C::NUM_EXP {
let j = bin - C::NUM_LINEAR;
let octave = j / 2;
let f = C::EXP_FLOOR.ilog2() as u64;
let base = 1u64 << (f + octave);
let raw = if j % 2 == 0 { base } else { base + base / 2 };
align_up(raw, C::MIN_ALIGN)
} else {
u64::MAX
}
}
#[inline]
pub(crate) const fn bin_index<C: Config>(size: u64) -> u64 {
let min = C::MIN_ALIGN;
if size <= C::LNR_FLOOR {
0
} else if size < C::EXP_FLOOR {
(size - C::LNR_FLOOR).div_ceil(min)
} else if size <= C::EXP_CEIL {
let m = size.ilog2() as u64; let base = 1u64 << m;
let f = C::EXP_FLOOR.ilog2() as u64;
let (octave, within) = if size == base {
(m - f, 0)
} else if size <= base + base / 2 {
(m - f, 1)
} else {
(m + 1 - f, 0)
};
C::NUM_LINEAR + 2 * octave + within
} else {
C::NUM_BINS - 1
}
}
pub struct CadAlloc<C: Config> {
_config: PhantomData<fn() -> C>,
}
impl<C: Config> Default for CadAlloc<C> {
#[inline]
fn default() -> Self {
Self::new()
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[repr(i32)]
pub enum InitError {
MisalignedHeap = 1,
HeapTooSmall = 2,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[repr(i32)]
pub enum VerifyError {
BadMagic = 1,
ConfigMismatch = 2,
}
impl<C: Config> CadAlloc<C> {
#[must_use]
#[inline]
pub const fn new() -> Self {
Self {
_config: PhantomData,
}
}
#[inline(always)]
fn magic_addr(&self) -> u64 {
C::heap_base()
}
#[inline(always)]
fn fingerprint_addr(&self) -> u64 {
C::heap_base() + 8
}
#[inline(always)]
fn bin_head(&self, k: u64) -> u64 {
C::heap_base() + META_BYTES + k * 8
}
#[inline(always)]
fn bump_addr(&self) -> u64 {
C::heap_base() + META_BYTES + C::NUM_BINS * 8
}
#[inline(always)]
fn lock_addr(&self) -> u64 {
C::heap_base() + META_BYTES + (C::NUM_BINS + 1) * 8
}
#[inline(always)]
const fn control_bytes() -> u64 {
align_up(META_BYTES + (C::NUM_BINS + 2) * 8, C::MIN_ALIGN)
}
#[inline(always)]
fn heap_end(&self) -> u64 {
C::heap_base() + C::heap_size()
}
#[inline(always)]
const fn oversize_bin() -> u64 {
C::NUM_BINS - 1
}
#[inline]
const fn floor_bin(size: u64) -> u64 {
let ceil = bin_index::<C>(size);
if bin_class::<C>(ceil) <= size {
ceil
} else {
ceil - 1
}
}
#[inline]
const fn is_block_exact(size: u64) -> bool {
size > C::EXP_CEIL || bin_class::<C>(bin_index::<C>(size)) == size
}
#[inline]
const fn align_of_bin(bin: u64) -> u64 {
if bin < C::NUM_LINEAR {
C::MIN_ALIGN
} else if bin < C::NUM_LINEAR + C::NUM_EXP {
let octave = (bin - C::NUM_LINEAR) / 2;
let base_log2 = C::EXP_FLOOR.ilog2() as u64 + octave;
let align = 1u64 << (base_log2 - 1);
if align < C::MIN_ALIGN {
C::MIN_ALIGN
} else {
align
}
} else {
C::EXP_CEIL
}
}
#[inline(always)]
fn load(&self, addr: u64) -> u64 {
unsafe { C::Atomics::atomic_load(addr) }
}
#[inline(always)]
fn store(&self, addr: u64, val: u64) {
unsafe { C::Atomics::atomic_store(addr, val) }
}
#[inline(always)]
fn cas_weak(&self, addr: u64, current: u64, new: u64) -> bool {
unsafe { C::Atomics::atomic_cas_weak(addr, current, new) }.1
}
#[inline]
fn lock(&self) {
let addr = self.lock_addr();
while !self.cas_weak(addr, 0, 1) {
spin_loop();
}
}
#[inline]
fn unlock(&self) {
self.store(self.lock_addr(), 0);
}
#[inline]
pub(crate) fn push_fixed(&self, k: u64, block: u64) {
let head = self.bin_head(k);
let mask = C::MIN_ALIGN - 1;
loop {
let old = self.load(head);
let old_addr = old & !mask;
let new_tag = (old + 1) & mask;
self.store(block + 8, old_addr); if self.cas_weak(head, old, block | new_tag) {
return;
}
}
}
#[inline]
pub(crate) fn pop_fixed(&self, k: u64) -> u64 {
let head = self.bin_head(k);
let mask = C::MIN_ALIGN - 1;
loop {
let old = self.load(head);
let old_addr = old & !mask;
if old_addr == 0 {
return 0;
}
let next = self.load(old_addr + 8);
let new_tag = (old + 1) & mask;
if self.cas_weak(head, old, next | new_tag) {
return old_addr;
}
}
}
#[must_use]
#[inline]
pub const fn magic() -> u64 {
MAGIC
}
#[must_use]
#[inline]
pub const fn config_hash() -> u64 {
config_fingerprint::<C>()
}
#[inline]
pub fn init(&self) -> Result<(), InitError> {
let base = C::heap_base();
if base & (C::MIN_ALIGN - 1) != 0 {
return Err(InitError::MisalignedHeap);
}
if C::heap_size() < Self::control_bytes() {
return Err(InitError::HeapTooSmall);
}
self.store(self.magic_addr(), MAGIC);
self.store(self.fingerprint_addr(), config_fingerprint::<C>());
let mut k = 0;
while k < C::NUM_BINS {
self.store(self.bin_head(k), 0);
k += 1;
}
self.store(self.bump_addr(), base + Self::control_bytes());
self.store(self.lock_addr(), 0);
Ok(())
}
#[inline]
pub fn verify(&self) -> Result<(), VerifyError> {
if self.load(self.magic_addr()) != MAGIC {
return Err(VerifyError::BadMagic);
}
if self.load(self.fingerprint_addr()) != config_fingerprint::<C>() {
return Err(VerifyError::ConfigMismatch);
}
Ok(())
}
#[inline]
const fn request_block_size(size: u64) -> u64 {
let need = align_up(size, C::MIN_ALIGN) + C::MIN_ALIGN; let bin = bin_index::<C>(need);
if bin == Self::oversize_bin() {
need
} else {
bin_class::<C>(bin)
}
}
#[must_use]
#[inline]
pub fn alloc(&self, size: u64) -> Slice {
let need = align_up(size, C::MIN_ALIGN) + C::MIN_ALIGN; let bin = bin_index::<C>(need);
let block = if bin == Self::oversize_bin() {
self.alloc_oversize(need)
} else {
self.alloc_fixed(bin)
};
if block == 0 {
return Slice::NULL;
}
let bsize = header_size(self.load(block));
unsafe { Slice::new(block + C::MIN_ALIGN, bsize - C::MIN_ALIGN) }
}
#[inline]
pub fn free(&self, block: Slice) {
if block.is_null() {
return;
}
let hdr = block.ptr - C::MIN_ALIGN;
let header = self.load(hdr);
if header_is_free(header) {
debug_assert!(false, "cadalloc: double free or invalid slice");
return;
}
let size = header_size(header);
let bin = bin_index::<C>(size);
self.store(hdr, pack(size, FREE));
if bin == Self::oversize_bin() {
self.lock();
self.push_oversize_locked(hdr);
self.unlock();
} else {
self.push_fixed(bin, hdr);
}
}
#[inline]
pub fn realloc(&self, block: Slice, new_size: u64) -> Slice {
if block.is_null() {
return self.alloc(new_size);
}
let hdr = block.ptr - C::MIN_ALIGN;
let cur_size = header_size(self.load(hdr));
let target = Self::request_block_size(new_size);
if cur_size >= target {
if cur_size - target < C::SPLIT_MIN {
return unsafe { Slice::new(block.ptr, cur_size - C::MIN_ALIGN) };
}
self.lock();
let alloc_size = self.split_and_free_tail(hdr, cur_size, target);
self.unlock();
return unsafe { Slice::new(block.ptr, alloc_size - C::MIN_ALIGN) };
}
self.relocate(block, cur_size - C::MIN_ALIGN, self.alloc(new_size))
}
#[inline]
fn relocate(&self, src: Slice, src_usable: u64, dst: Slice) -> Slice {
if dst.is_null() {
return Slice::NULL;
}
let copy = if src_usable < dst.len {
src_usable
} else {
dst.len
};
unsafe {
core::ptr::copy_nonoverlapping(src.ptr as *const u8, dst.ptr as *mut u8, copy as usize);
}
self.free(src);
dst
}
#[inline]
fn alloc_fixed(&self, bin: u64) -> u64 {
let class = bin_class::<C>(bin);
let block = self.pop_fixed(bin);
if block != 0 {
self.store(block, pack(class, USED));
return block;
}
let align = Self::align_of_bin(bin);
self.lock();
let mut block = self.pop_fixed(bin);
if block == 0 {
let bump = self.load(self.bump_addr());
let aligned = align_up(bump, align);
if aligned + class <= self.heap_end() {
self.carve_gap(bump, aligned);
self.store(self.bump_addr(), aligned + class);
block = aligned;
}
}
self.unlock();
if block != 0 {
self.store(block, pack(class, USED));
}
block
}
#[inline]
fn push_oversize_locked(&self, addr: u64) {
let head = self.bin_head(Self::oversize_bin());
self.store(addr + 8, self.load(head));
self.store(head, addr);
}
#[inline]
pub(crate) const fn largest_carvable(end: u64, len: u64) -> (u64, u64) {
if len < C::LNR_FLOOR {
return (0, 0);
}
let mut cap = len;
if len > C::EXP_CEIL {
let start = align_up(end - len, C::EXP_CEIL);
let size = end - start;
if size > C::EXP_CEIL {
return (size, Self::oversize_bin());
}
cap = C::EXP_CEIL;
}
let limit = if cap < C::EXP_FLOOR {
cap
} else {
let exp_cap = 3 * (1u64 << end.trailing_zeros());
if cap < exp_cap {
cap
} else if exp_cap >= C::EXP_FLOOR {
exp_cap
} else {
C::EXP_FLOOR - C::MIN_ALIGN
}
};
if limit < C::LNR_FLOOR {
return (0, 0);
}
let bin = Self::floor_bin(limit);
(bin_class::<C>(bin), bin)
}
#[inline]
fn carve_gap(&self, lo: u64, hi: u64) {
let mut end = hi;
while end - lo >= C::MIN_ALIGN {
let (size, bin) = Self::largest_carvable(end, end - lo);
if size == 0 {
break;
}
end -= size;
self.store(end, pack(size, FREE));
if bin == Self::oversize_bin() {
self.push_oversize_locked(end);
} else {
self.push_fixed(bin, end);
}
}
}
#[inline]
fn split_and_free_tail(&self, block: u64, bsize: u64, need: u64) -> u64 {
if bsize - need < C::SPLIT_MIN {
self.store(block, pack(bsize, USED));
return bsize;
}
let ptr = block + need;
let mut end = block + bsize;
let mut iter = 0;
while end - ptr >= C::MIN_ALIGN
&& (iter < C::CARVE_MAX || !Self::is_block_exact(end - block))
{
let (size, bin) = Self::largest_carvable(end, end - ptr);
if size == 0 {
break;
}
end -= size;
self.store(end, pack(size, FREE));
if bin == Self::oversize_bin() {
self.push_oversize_locked(end);
} else {
self.push_fixed(bin, end);
}
iter += 1;
}
let mut alloc_size = end - block;
if !Self::is_block_exact(alloc_size) {
alloc_size = bin_class::<C>(Self::floor_bin(alloc_size));
}
debug_assert!(
alloc_size > C::EXP_CEIL
|| block & (Self::align_of_bin(bin_index::<C>(alloc_size)) - 1) == 0,
"cadalloc: retained block not aligned to its class"
);
self.store(block, pack(alloc_size, USED));
alloc_size
}
#[inline]
fn alloc_oversize(&self, need: u64) -> u64 {
self.lock();
let head = self.bin_head(Self::oversize_bin());
let mut prev_link = head;
let mut cur = self.load(head);
let mut chosen = 0;
let mut chosen_prev_link = 0;
while cur != 0 {
if header_size(self.load(cur)) >= need {
chosen = cur;
chosen_prev_link = prev_link;
break;
}
prev_link = cur + 8;
cur = self.load(cur + 8);
}
let block = if chosen != 0 {
self.store(chosen_prev_link, self.load(chosen + 8)); let bsize = header_size(self.load(chosen));
self.split_and_free_tail(chosen, bsize, need);
chosen
} else {
let bump = self.load(self.bump_addr());
let aligned = align_up(bump, C::EXP_CEIL);
if aligned + need > self.heap_end() {
0
} else {
self.carve_gap(bump, aligned);
self.store(self.bump_addr(), aligned + need);
self.store(aligned, pack(need, USED));
aligned
}
};
self.unlock();
block
}
}