#![no_std]
#![feature(const_generics)]
#![allow(incomplete_features)]
use core::mem::MaybeUninit;
use alloc_wg::alloc::{AllocErr, AllocInit, AllocRef, Layout, MemoryBlock, ReallocPlacement};
use core::{
ops::Index,
ptr::NonNull,
sync::atomic::{AtomicBool, Ordering},
};
pub struct BuddyAllocator<AR: AllocRef, const BLOCK_SIZE: usize, const ORDER: usize> {
allocator: AR,
memory: Option<MemoryBlock>,
buddys: Buddys<{ Self::USED_SIZE }>,
}
impl<AR: AllocRef, const BLOCK_SIZE: usize, const ORDER: usize>
BuddyAllocator<AR, BLOCK_SIZE, ORDER>
{
const USED_SIZE: usize = (1 << (ORDER + 1)) - 1;
const ENTIRE_SIZE: usize = (1 << ORDER) * BLOCK_SIZE;
pub fn try_new(allocator: AR) -> Result<Self, AllocErr> {
assert!(
BLOCK_SIZE.is_power_of_two(),
"BLOCK_SIZE must be a power of two"
);
assert!(ORDER != 0, "ORDER must not be zero");
let layout =
Layout::from_size_align(Self::ENTIRE_SIZE, Self::ENTIRE_SIZE).map_err(|_| AllocErr)?;
let memory = allocator
.alloc(layout, AllocInit::Uninitialized)
.map(Some)?;
Ok(BuddyAllocator {
allocator,
memory,
buddys: Buddys::new(),
})
}
pub unsafe fn is_unused(&self) -> bool {
self.buddys.allocate(0).is_some()
}
pub fn base_address(&self) -> NonNull<u8> {
self.memory.as_ref().unwrap().ptr()
}
pub fn capacitiy(&self) -> usize {
Self::ENTIRE_SIZE
}
fn level_and_size(&self, size: usize) -> (usize, usize) {
let blocks_size = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
let blocks_size = blocks_size.max(1).next_power_of_two();
let level = ORDER - blocks_size.trailing_zeros() as usize - 1;
debug_assert!(level < ORDER, "size: {}", size);
let block_size = BLOCK_SIZE * (1 << (ORDER - level - 1));
(level, block_size)
}
fn location(&self, ptr: NonNull<u8>, size: usize) -> (usize, usize) {
let addr = ptr.as_ptr() as usize;
let memory = self.memory.as_ref().unwrap();
let blocks_addr = memory.ptr().as_ptr() as usize;
debug_assert!(addr >= blocks_addr);
debug_assert!(addr + size <= blocks_addr + Self::ENTIRE_SIZE);
let (level, block_size) = self.level_and_size(size);
let inner_addr = addr & (Self::ENTIRE_SIZE - 1);
let idx = inner_addr / block_size;
let block_mask = block_size - 1;
debug_assert_eq!(inner_addr & block_mask, 0, "block is placed incorrectly",);
(level, idx)
}
fn calc_address(&self, idx: usize, level: usize) -> NonNull<u8> {
let memory = self.memory.as_ref().unwrap();
let ptr = memory.ptr().as_ptr() as usize;
let block_size = BLOCK_SIZE * (1 << (ORDER - level - 1));
let offset = block_size * idx;
NonNull::new((ptr + offset) as *const u8 as *mut _).unwrap()
}
}
unsafe impl<AR: AllocRef, const BLOCK_SIZE: usize, const ORDER: usize> AllocRef
for &BuddyAllocator<AR, BLOCK_SIZE, ORDER>
{
fn alloc(self, layout: Layout, init: AllocInit) -> Result<MemoryBlock, AllocErr> {
let old_align = layout.align();
let size = layout.size().max(layout.align()).max(1);
let (level, block_size) = self.level_and_size(size);
let idx = self.buddys.allocate(level).ok_or(AllocErr)?;
let ptr = self.calc_address(idx, level);
let new_layout = Layout::from_size_align(block_size, old_align).unwrap();
let mut memory = unsafe { MemoryBlock::new(ptr, new_layout) };
memory.init(init);
Ok(memory)
}
unsafe fn dealloc(self, memory: MemoryBlock) {
let (level, idx) = self.location(memory.ptr(), memory.layout().size());
self.buddys.deallocate(idx, level);
}
unsafe fn grow(
self,
memory: &mut MemoryBlock,
new_size: usize,
placement: ReallocPlacement,
init: AllocInit,
) -> Result<(), AllocErr> {
let old_align = memory.align();
let old_size = memory.size();
let old_ptr = memory.ptr();
let size = old_align.max(old_size);
let (old_level, old_idx) = self.location(old_ptr, size);
let (new_level, block_size) = self.level_and_size(new_size);
if new_level > old_level {
return Err(AllocErr);
}
let idx = self
.buddys
.grow(old_idx, old_level, new_level, placement)
.ok_or(AllocErr)?;
let new_ptr = self.calc_address(idx, new_level);
if let AllocInit::Zeroed = init {
let old_start = old_ptr.as_ptr() as usize;
let old_end = old_start + old_size;
let new_start = new_ptr.as_ptr() as usize;
let new_end = new_start + block_size;
if new_start < old_start {
let offset = old_start - new_start;
new_ptr.as_ptr().write_bytes(0, offset);
}
if new_end > old_end {
let offset = new_end - old_end;
old_ptr.as_ptr().add(old_end).write_bytes(0, offset);
}
}
let new_layout = Layout::from_size_align(block_size, block_size).unwrap();
*memory = MemoryBlock::new(new_ptr, new_layout);
Ok(())
}
unsafe fn shrink(
self,
memory: &mut MemoryBlock,
new_size: usize,
_placement: ReallocPlacement,
) -> Result<(), AllocErr> {
let (old_level, old_idx) = self.location(memory.ptr(), memory.layout().size());
let (new_level, block_size) = self.level_and_size(new_size);
if new_level < old_level {
return Err(AllocErr);
}
self.buddys.shrink(old_idx, old_level, new_level);
let new_layout = Layout::from_size_align_unchecked(block_size, memory.align());
*memory = MemoryBlock::new(memory.ptr(), new_layout);
Ok(())
}
}
impl<AR: AllocRef, const BLOCK_SIZE: usize, const ORDER: usize> Drop
for BuddyAllocator<AR, BLOCK_SIZE, ORDER>
{
fn drop(&mut self) {
let memory = self.memory.take().unwrap();
unsafe {
self.allocator.dealloc(memory);
}
}
}
struct Buddys<const BLOCKS: usize>([AtomicBool; BLOCKS]);
impl<const BLOCKS: usize> Buddys<BLOCKS> {
fn new() -> Self {
let blocks: Self = unsafe { MaybeUninit::zeroed().assume_init() };
for i in 0..BLOCKS {
blocks.0[i].store(i == 0, Ordering::Relaxed);
}
blocks
}
fn allocate(&self, level: usize) -> Option<usize> {
for idx in 0..1 << level {
let was_available = self[(level, idx)].compare_and_swap(true, false, Ordering::Relaxed);
if was_available {
return Some(idx);
}
}
if level != 0 {
if let Some(idx) = self.allocate(level - 1) {
let idx = idx << 1;
self[(level, idx ^ 1)].store(true, Ordering::Relaxed);
return Some(idx);
}
}
None
}
fn deallocate(&self, idx: usize, level: usize) {
if level != 0 {
let was_available =
self[(level, idx ^ 1)].compare_and_swap(true, false, Ordering::Relaxed);
if was_available {
self.deallocate(idx >> 1, level - 1);
return;
}
}
self[(level, idx)].store(true, Ordering::Relaxed);
}
fn shrink(&self, idx: usize, old_level: usize, new_level: usize) {
let level_diff = new_level - old_level;
for i in 0..level_diff {
self[(old_level + i, (idx << i) ^ 1)].store(true, Ordering::Relaxed);
}
}
fn grow(
&self,
idx: usize,
old_level: usize,
new_level: usize,
placement: ReallocPlacement,
) -> Option<usize> {
let level_diff = old_level - new_level;
if let ReallocPlacement::InPlace = placement {
if idx & ((2 << level_diff) - 1) != 0 {
return None;
}
}
for i in 0..level_diff {
let was_available = self[(old_level - i, (idx >> i) ^ 1)].compare_and_swap(
true,
false,
Ordering::Relaxed,
);
if !was_available {
for i in 0..i {
self[(old_level - i, (idx >> i) ^ 1)].store(true, Ordering::Relaxed);
}
return None;
}
}
Some(idx >> level_diff)
}
}
impl<const BLOCKS: usize> Index<(usize, usize)> for Buddys<BLOCKS> {
type Output = AtomicBool;
fn index(&self, (level, idx): (usize, usize)) -> &AtomicBool {
debug_assert!(
idx < 1 << level,
"trying to access child {} at level {}",
idx,
level
);
debug_assert!(
BLOCKS >= 1 << level,
"level {} is too big for {} blocks",
level,
BLOCKS
);
let base = (1 << level) - 1;
let idx = base + idx;
&self.0[idx]
}
}