use alloc::rc::Rc;
use alloc::vec::Vec;
use core::cell::RefCell;
use fixedbitset::FixedBitSet;
use smallvec::SmallVec;
use super::{AllocError, Allocation};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SlotLayout {
base_addr: u64,
slot_size: u32,
slot_count: usize,
}
impl SlotLayout {
pub fn new(base_addr: u64, slot_size: usize, slot_count: usize) -> Result<Self, AllocError> {
let slot_size = u32::try_from(slot_size).map_err(|_| AllocError::InvalidArg)?;
if slot_size == 0 {
return Err(AllocError::InvalidArg);
}
if slot_count == 0 {
return Err(AllocError::EmptyRegion);
}
let byte_len = (slot_size as usize)
.checked_mul(slot_count)
.ok_or(AllocError::Overflow)?;
base_addr
.checked_add(u64::try_from(byte_len).map_err(|_| AllocError::Overflow)?)
.ok_or(AllocError::Overflow)?;
core::alloc::Layout::array::<u64>(slot_count).map_err(|_| AllocError::Overflow)?;
Ok(Self {
base_addr,
slot_size,
slot_count,
})
}
pub const fn base_addr(self) -> u64 {
self.base_addr
}
pub const fn slot_size(self) -> usize {
self.slot_size as usize
}
pub const fn slot_count(self) -> usize {
self.slot_count
}
pub const fn byte_len(self) -> usize {
self.slot_size as usize * self.slot_count
}
pub const fn end_addr(self) -> u64 {
self.base_addr + self.byte_len() as u64
}
}
struct Tier {
base_addr: u64,
slot_size: u32,
count: usize,
free: SmallVec<[u64; 64]>,
allocated: FixedBitSet,
}
impl Tier {
fn from_layout(layout: SlotLayout) -> Result<Self, AllocError> {
let mut free = SmallVec::new();
free.try_reserve_exact(layout.slot_count)
.map_err(|_| AllocError::Bookkeeping)?;
for i in 0..layout.slot_count {
free.push(layout.base_addr + (i * layout.slot_size as usize) as u64);
}
Ok(Self {
base_addr: layout.base_addr,
slot_size: layout.slot_size,
count: layout.slot_count,
free,
allocated: FixedBitSet::with_capacity(layout.slot_count),
})
}
fn end(&self) -> u64 {
self.base_addr + self.count as u64 * u64::from(self.slot_size)
}
fn contains(&self, addr: u64) -> bool {
(self.base_addr..self.end()).contains(&addr)
}
fn slot_of(&self, addr: u64) -> Result<usize, AllocError> {
if !self.contains(addr) {
return Err(AllocError::InvalidFree(addr, 0));
}
let off = addr - self.base_addr;
if !off.is_multiple_of(u64::from(self.slot_size)) {
return Err(AllocError::InvalidFree(addr, 0));
}
Ok((off / u64::from(self.slot_size)) as usize)
}
fn live_slot_of(&self, addr: u64) -> Result<usize, AllocError> {
let slot = self.slot_of(addr)?;
if !self.allocated.contains(slot) {
return Err(AllocError::InvalidFree(addr, 0));
}
Ok(slot)
}
fn alloc(&mut self, len: usize) -> Result<Allocation, AllocError> {
if len == 0 {
return Err(AllocError::InvalidArg);
}
if len > self.slot_size as usize {
return Err(AllocError::OutOfMemory);
}
let addr = self.free.pop().ok_or(AllocError::NoSpace)?;
self.allocated
.insert(((addr - self.base_addr) / u64::from(self.slot_size)) as usize);
Ok(Allocation {
addr,
len: self.slot_size,
})
}
fn dealloc_addr(&mut self, addr: u64) -> Result<(), AllocError> {
let slot = self.live_slot_of(addr)?;
self.allocated.set(slot, false);
self.free.push(addr);
Ok(())
}
fn reserve_addr(&mut self, addr: u64) -> Result<(), AllocError> {
let slot = self.slot_of(addr)?;
if self.allocated.contains(slot) {
return Err(AllocError::InvalidArg);
}
self.allocated.insert(slot);
Ok(())
}
fn rebuild_free(&mut self) {
self.free.clear();
for slot in self.allocated.zeroes() {
self.free
.push(self.base_addr + slot as u64 * u64::from(self.slot_size));
}
}
fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
self.live_slot_of(addr)?;
Ok(self.slot_size as usize)
}
fn slot_addr(&self, index: usize) -> Option<u64> {
(index < self.count).then(|| self.base_addr + (index * self.slot_size as usize) as u64)
}
fn num_free(&self) -> usize {
self.free.len()
}
fn append_live_addrs(&self, addrs: &mut Vec<u64>) {
addrs.extend(
self.allocated
.ones()
.map(|slot| self.base_addr + (slot * self.slot_size as usize) as u64),
);
}
fn layout(&self) -> SlotLayout {
SlotLayout {
base_addr: self.base_addr,
slot_size: self.slot_size,
slot_count: self.count,
}
}
}
struct Inner {
lower: Option<Tier>,
upper: Tier,
generation: u64,
}
impl Inner {
fn new(lower: Option<SlotLayout>, upper: SlotLayout) -> Result<Self, AllocError> {
let Some(lower) = lower else {
return Ok(Self {
lower: None,
upper: Tier::from_layout(upper)?,
generation: 0,
});
};
if lower.slot_size > upper.slot_size || lower.end_addr() > upper.base_addr {
return Err(AllocError::InvalidArg);
}
if lower.slot_size == upper.slot_size {
if lower.end_addr() != upper.base_addr {
return Err(AllocError::InvalidArg);
}
let count = lower
.slot_count
.checked_add(upper.slot_count)
.ok_or(AllocError::Overflow)?;
let layout = SlotLayout::new(lower.base_addr, lower.slot_size(), count)?;
return Ok(Self {
lower: None,
upper: Tier::from_layout(layout)?,
generation: 0,
});
}
Ok(Self {
lower: Some(Tier::from_layout(lower)?),
upper: Tier::from_layout(upper)?,
generation: 0,
})
}
fn max_alloc_len(&self) -> usize {
self.upper.slot_size as usize
}
fn alloc(&mut self, len: usize) -> Result<Allocation, AllocError> {
if let Some(lower) = &mut self.lower
&& len <= lower.slot_size as usize
{
match lower.alloc(len) {
Ok(alloc) => return Ok(alloc),
Err(AllocError::NoSpace) => {}
Err(err) => return Err(err),
}
}
self.upper.alloc(len)
}
fn dealloc_addr(&mut self, addr: u64) -> Result<(), AllocError> {
if let Some(lower) = &mut self.lower
&& lower.contains(addr)
{
return lower.dealloc_addr(addr);
}
self.upper.dealloc_addr(addr)
}
fn retire_generation(
&mut self,
reserved: impl Iterator<Item = u64> + Clone,
) -> Result<(), AllocError> {
let generation = self.generation.checked_add(1).ok_or(AllocError::Overflow)?;
#[cfg(debug_assertions)]
for addr in reserved.clone() {
debug_assert!(
self.allocation_len(addr).is_ok(),
"address {addr:#x} is not a live pool slot"
);
}
self.generation = generation;
self.upper.allocated.clear();
if let Some(lower) = &mut self.lower {
lower.allocated.clear();
}
for addr in reserved {
if let Some(lower) = &mut self.lower
&& lower.contains(addr)
{
lower.reserve_addr(addr)?;
} else {
self.upper.reserve_addr(addr)?;
}
}
self.upper.rebuild_free();
if let Some(lower) = &mut self.lower {
lower.rebuild_free();
}
Ok(())
}
fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
if let Some(lower) = &self.lower
&& lower.contains(addr)
{
return lower.allocation_len(addr);
}
self.upper.allocation_len(addr)
}
fn slot_addr(&self, index: usize) -> Option<u64> {
if let Some(lower) = &self.lower {
if index < lower.count {
return lower.slot_addr(index);
}
return self.upper.slot_addr(index - lower.count);
}
self.upper.slot_addr(index)
}
fn live_addrs(&self) -> Vec<u64> {
let mut addrs = Vec::with_capacity(self.num_live());
if let Some(lower) = &self.lower {
lower.append_live_addrs(&mut addrs);
}
self.upper.append_live_addrs(&mut addrs);
addrs
}
fn base_addr(&self) -> u64 {
self.lower
.as_ref()
.map_or(self.upper.base_addr, |lower| lower.base_addr)
}
fn count(&self) -> usize {
self.lower.as_ref().map_or(0, |lower| lower.count) + self.upper.count
}
fn num_free(&self) -> usize {
self.lower.as_ref().map_or(0, Tier::num_free) + self.upper.num_free()
}
fn num_live(&self) -> usize {
self.count() - self.num_free()
}
fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
(self.lower.as_ref().map(Tier::layout), self.upper.layout())
}
fn byte_len(&self) -> usize {
(self.upper.layout().end_addr() - self.base_addr()) as usize
}
}
#[derive(Clone)]
pub struct SlotPool {
inner: Rc<RefCell<Inner>>,
}
impl SlotPool {
pub(crate) fn generation(&self) -> u64 {
self.inner.borrow().generation
}
pub(crate) unsafe fn retire_generation(
&self,
reserved: impl Iterator<Item = u64> + Clone,
) -> Result<(), AllocError> {
self.inner.borrow_mut().retire_generation(reserved)
}
pub fn new(layout: SlotLayout) -> Result<Self, AllocError> {
Self::from_layouts(None, layout)
}
pub fn new_tiered(lower: SlotLayout, upper: SlotLayout) -> Result<Self, AllocError> {
Self::from_layouts(Some(lower), upper)
}
fn from_layouts(lower: Option<SlotLayout>, upper: SlotLayout) -> Result<Self, AllocError> {
let inner = Inner::new(lower, upper)?;
Ok(Self {
inner: Rc::new(RefCell::new(inner)),
})
}
pub fn live_addrs(&self) -> Vec<u64> {
self.inner.borrow().live_addrs()
}
pub fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
self.inner.borrow().layouts()
}
pub fn slot_addr(&self, index: usize) -> Option<u64> {
self.inner.borrow().slot_addr(index)
}
pub fn num_free(&self) -> usize {
self.inner.borrow().num_free()
}
pub fn num_live(&self) -> usize {
self.inner.borrow().num_live()
}
pub fn num_free_lower(&self) -> usize {
self.inner.borrow().lower.as_ref().map_or(0, Tier::num_free)
}
pub fn num_free_upper(&self) -> usize {
self.inner.borrow().upper.num_free()
}
pub fn dealloc(&self, addr: u64) -> Result<(), AllocError> {
self.inner.borrow_mut().dealloc_addr(addr)
}
pub fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
self.inner.borrow().allocation_len(addr)
}
pub fn base_addr(&self) -> u64 {
self.inner.borrow().base_addr()
}
pub fn slot_size(&self) -> usize {
self.inner.borrow().max_alloc_len()
}
pub fn lower_slot_size(&self) -> Option<usize> {
self.inner
.borrow()
.lower
.as_ref()
.map(|lower| lower.slot_size as usize)
}
pub fn upper_slot_size(&self) -> usize {
self.inner.borrow().upper.slot_size as usize
}
pub fn count(&self) -> usize {
self.inner.borrow().count()
}
pub fn alloc(&self, len: usize) -> Result<Allocation, AllocError> {
self.inner.borrow_mut().alloc(len)
}
pub fn byte_len(&self) -> usize {
self.inner.borrow().byte_len()
}
#[cfg(test)]
pub(crate) fn strong_count(&self) -> usize {
Rc::strong_count(&self.inner)
}
}