#![feature(const_fn)]
#![feature(allocator_api)]
#![feature(alloc_layout_extra)]
#![cfg_attr(not(test), no_std)]
extern crate alloc;
use alloc::alloc::{AllocErr, Layout};
use core::mem::{self, size_of};
use core::ptr::NonNull;
mod region;
pub use self::region::{Region, RegionFlags};
mod region_iter;
pub use self::region_iter::AllocatorRegionIterator;
mod align;
pub use self::align::{align_down, align_up};
mod locked;
pub use self::locked::LockedAllocator;
#[cfg(test)]
mod region_iter_test;
#[cfg(test)]
mod test;
pub struct Allocator {
pub first_region: usize,
}
impl Allocator {
pub const fn empty() -> Allocator {
Allocator { first_region: 0 }
}
pub fn min_allocation_size() -> usize {
size_of::<usize>() * 4
}
pub fn free_bytes(&self) -> usize {
let mut free = 0;
for r in self.iter() {
if !r.get_used() {
free += r.size();
}
}
free
}
pub unsafe fn add_region(&mut self, addr: usize, size: usize) {
if size <= Region::min_size() {
return;
}
let mut region = Region::new(addr, size);
if self.first_region != 0 {
let mut last = self.get_region_first().unwrap();
loop {
if last.next == 0 {
break;
}
last = self.get_region_for_ptr(last.next as *mut u8).unwrap();
}
last.next = addr;
region.prev = last.data - size_of::<Region>();
region.next = 0;
} else {
self.first_region = addr;
}
let ptr = addr as *mut Region;
ptr.write(region);
}
pub fn iter(&self) -> AllocatorRegionIterator {
AllocatorRegionIterator::new(&self)
}
pub fn get_region_first(&self) -> Option<&mut Region> {
if self.first_region == 0 {
return None;
}
unsafe { Some(&mut *(self.first_region as *mut Region)) }
}
pub fn get_region_first_free(&self, size: usize) -> Option<&mut Region> {
let mut region = self.get_region_first();
loop {
if let Some(ref r) = region {
if r.get_used() == false && r.size() >= size {
break;
}
} else {
break;
}
match region {
Some(r) => {
region = self.get_region_for_ptr(r.next as *mut u8);
}
None => {
break;
}
}
}
region
}
pub fn get_region_for_ptr(&self, ptr: *mut u8) -> Option<&mut Region> {
if let Some(r) = self.get_region_first() {
let mut region = r;
loop {
match unsafe { region.header_ptr() } {
Some(p) if p.as_ptr() == ptr => return Some(region),
Some(_) => {}
None => return None,
};
if region.next == 0 {
break;
}
region = unsafe { &mut *(region.next as *mut Region) };
}
}
None
}
pub fn get_region_for_data_ptr(&self, ptr: *mut u8) -> Option<&mut Region> {
if let Some(r) = self.get_region_first() {
let mut region = r;
loop {
match unsafe { region.data_ptr() } {
Some(p) if p.as_ptr() == ptr => return Some(region),
Some(_) => {}
None => return None,
};
if region.next == 0 {
break;
}
region = unsafe { &mut *(region.next as *mut Region) };
}
}
None
}
pub fn combine_regions(&self, ptr: *mut u8) {
let mut region = self
.get_region_for_ptr(ptr)
.expect("combine: failed to get initial region");
loop {
if region.prev == 0 {
break;
}
let prev = self.get_region_for_ptr(region.prev as *mut u8);
if prev.is_none() {
break;
}
let mut prev = prev.unwrap();
if prev.get_used() {
break;
}
let expect_region = prev.data + prev.size();
match unsafe { region.header_ptr() } {
Some(r) if r.as_ptr() as usize == expect_region => {}
Some(_) | None => {
break;
}
};
prev.size = prev.size() + region.size() + size_of::<Region>();
prev.padding_start = 0;
prev.padding_end = 0;
prev.next = region.next;
if let Some(ref mut pp) = self.get_region_for_ptr(prev.prev as *mut u8) {
pp.next = unsafe { prev.header_ptr().unwrap().as_ptr() } as usize;
}
let hdrptr = unsafe { prev.header_ptr().unwrap().as_ptr() };
region = self
.get_region_for_ptr(hdrptr)
.expect("combine: failed to get next region");
}
loop {
if region.next == region.data + region.size() {
let nextregion = self
.get_region_for_ptr(region.next as *mut u8)
.expect("combine: failed to get next region");
if nextregion.get_used() {
break;
}
let size = region.size() + nextregion.size() + size_of::<Region>();
let next = nextregion.next;
core::mem::drop(nextregion);
region.size = size;
region.next = next;
} else {
break;
}
}
}
pub fn allocate(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
let mut size = layout.size();
if size < Self::min_allocation_size() {
size = Self::min_allocation_size();
}
size = align_up(size, mem::align_of::<Region>());
let layout = Layout::from_size_align(size, layout.align()).unwrap();
let size_pad = layout.padding_needed_for(layout.align()) + layout.size();
let region = self.get_region_first_free(size_pad);
if region.is_none() {
return Err(AllocErr);
}
let mut region = region.unwrap();
region.set_used(true);
region.padding_start = size_pad - layout.size();
if (layout.size() + Region::min_size()) <= region.size() {
let data_addr = region.data + layout.size();
let new_size = region.size() - layout.size();
let mut new_region = Region::new(data_addr, new_size);
new_region.next = region.next;
new_region.prev = region.data - size_of::<Region>();
unsafe {
let ptr = data_addr as *mut Region;
ptr.write(new_region);
region.next = ptr as usize;
}
region.size = layout.size();
}
Ok(unsafe { region.data_ptr().unwrap() })
}
pub fn deallocate(&mut self, ptr: NonNull<u8>, _layout: Layout) {
let region = self
.get_region_for_data_ptr(ptr.as_ptr())
.expect("failed to get region for given pointer");
let size = region.size();
region.padding_start = 0;
region.padding_end = 0;
region.size = size;
region.set_used(false);
unsafe {
self.combine_regions(region.header_ptr().unwrap().as_ptr());
}
}
}