polymorph-allocator 0.1.0

#[cfg(not(any(test, rustdoc)))]
use alloc::prelude::v1::*;
#[cfg(any(test, rustdoc))]
use std::prelude::v1::*;

use super::{Allocator, Region};
use alloc::alloc::Layout;
use core::mem::size_of;

#[test]
fn add_region_single() {
    const HEAP_SIZE: usize = 1024;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    let mut allocator = Allocator::empty();
    unsafe {
        // Add region
        allocator.add_region(heap as usize, HEAP_SIZE);

        // Check the data pointer is where we want it to be
        let region = allocator.get_region_first().unwrap();
        assert_eq!(
            region.data_ptr().unwrap().as_ptr(),
            heap.offset(size_of::<Region>() as isize)
        );
    }

    // Destroy heap box
    core::mem::drop(allocator);
    core::mem::drop(unsafe { Box::from_raw(heap) });
}

#[test]
fn add_region_multiple() {
    const HEAP_SIZE: usize = 1024;
    let heap_one = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;
    let heap_two = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap_one as usize, HEAP_SIZE);
        allocator.add_region(heap_two as usize, HEAP_SIZE);

        let region_one = allocator.get_region_first().unwrap();
        assert_eq!(
            region_one.data_ptr().unwrap().as_ptr(),
            heap_one.offset(size_of::<Region>() as isize)
        );

        let region_two = allocator.get_region_for_ptr(region_one.next as *mut u8).unwrap();
        assert_eq!(
            region_two.data_ptr().unwrap().as_ptr(),
            heap_two.offset(size_of::<Region>() as isize)
        );
    }
}

#[test]
fn allocation_single() {
    const HEAP_SIZE: usize = 1024;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    // Set up allocator
    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap as usize, HEAP_SIZE);
    }

    // Do an allocation
    let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
    allocator.allocate(layout).expect("failed to allocate");

    // Check first region is used, and is now the size of 4x usize
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.get_used(), true);
    assert_eq!(region.size(), size_of::<usize>() * 4);

    // Check that the next region is free
    let next = allocator.get_region_for_ptr(region.next as *mut u8)
        .expect("failed to get next region");
    assert_eq!(next.get_used(), false);
}

#[test]
fn allocation_and_deallocation_multiple() {
    const HEAP_SIZE: usize = 4096;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    // Set up allocator
    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap as usize, HEAP_SIZE);
    }

    // Do allocations
    for _ in 0..100 {
        let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
        let ptr = allocator.allocate(layout).expect("failed to allocate");
        allocator.deallocate(ptr, layout);
    }
}

#[test]
fn allocation_and_deallocation_single() {
    const HEAP_SIZE: usize = 1024;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    // Set up allocator
    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap as usize, HEAP_SIZE);
    }

    // Do an allocation
    let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
    let ptr = allocator.allocate(layout).expect("failed to allocate");

    // Check first region is used, and is now the size of 4x usize
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.get_used(), true);
    assert_eq!(region.size(), size_of::<usize>() * 4);
    core::mem::drop(region);

    // Deallocate
    allocator.deallocate(ptr, layout);

    // Check region is now set as free
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.get_used(), false);
}

#[test]
fn allocation_and_deallocation_combines_forward() {
    const HEAP_SIZE: usize = 1024;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    // Set up allocator
    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap as usize, HEAP_SIZE);
    }

    // Get first region size
    let region = allocator.get_region_first().expect("failed to get region");
    let region_size = region.size();
    core::mem::drop(region);

    // Do an allocation
    let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
    let ptr = allocator.allocate(layout).expect("failed to allocate");

    // Check first region is used, and is now the size of 4x usize
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.get_used(), true);
    assert_eq!(region.size(), size_of::<usize>() * 4);

    // Check next region is free
    let next_region = allocator.get_region_for_ptr(region.next as *mut u8).unwrap();
    assert_eq!(next_region.get_used(), false);

    // Drop region references
    core::mem::drop(next_region);
    core::mem::drop(region);

    // Deallocate
    allocator.deallocate(ptr, layout);

    // Check first region has combined with the free region after it
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.size(), region_size);
    assert_eq!(region.get_used(), false);
}

#[test]
fn allocation_and_deallocation_combines_forward_recursively() {
    const HEAP_SIZE: usize = 1024;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    // Set up allocator
    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap as usize, HEAP_SIZE);
    }

    // Get first region size
    let region = allocator.get_region_first().expect("failed to get region");
    let region_size = region.size();
    core::mem::drop(region);

    // Do an allocation
    let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
    let ptr = allocator.allocate(layout).expect("failed to allocate");

    // Do an allocation and immediately mark it as free without running
    // deallocate() on it
    {
        let fptr = allocator.allocate(layout).expect("failed to allocate");
        let region = allocator
            .get_region_for_data_ptr(fptr.as_ptr())
            .expect("failed to get region");
        region.set_used(false);
    }

    // Deallocate first region
    allocator.deallocate(ptr, layout);

    // Check regions have been combined and the free size is back at the
    // original first region size
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.size(), region_size);
    assert_eq!(region.get_used(), false);
}

#[test]
fn allocation_and_deallocation_combines_backwards() {
    const HEAP_SIZE: usize = 1024;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    // Set up allocator
    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap as usize, HEAP_SIZE);
    }

    // Get first region size
    let region = allocator.get_region_first().expect("failed to get region");
    let region_size = region.size();
    core::mem::drop(region);

    // Do two allocations
    let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
    let ptr_one = allocator.allocate(layout).expect("failed to allocate");
    let ptr_two = allocator.allocate(layout).expect("failed to allocate");

    // Deallocate ptr_one, which should not combine anything
    allocator.deallocate(ptr_one, layout);

    // Deallocate ptr_two, which should combine the space from ptr_one and the
    // free space following
    allocator.deallocate(ptr_two, layout);

    // Check first region has combined with the free region after it
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.size(), region_size);
    assert_eq!(region.get_used(), false);
}

#[test]
fn allocation_and_deallocation_combines_backwards_recursively() {
    const HEAP_SIZE: usize = 1024;
    let heap = Box::into_raw(Box::new([0u8; HEAP_SIZE])) as *mut u8;

    // Set up allocator
    let mut allocator = Allocator::empty();
    unsafe {
        allocator.add_region(heap as usize, HEAP_SIZE);
    }

    // Get first region size
    let region = allocator.get_region_first().expect("failed to get region");
    let region_size = region.size();
    core::mem::drop(region);

    // Do three allocations and immediately mark them as free without running
    // deallocate() on them
    for _ in 0..3 {
        let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
        let fptr = allocator.allocate(layout).expect("failed to allocate");
        let region = allocator
            .get_region_for_data_ptr(fptr.as_ptr())
            .expect("failed to get region");
        region.set_used(false);
    }

    // Do an allocation and immediately deallocate it
    let layout = Layout::from_size_align(size_of::<usize>() * 4, 1).unwrap();
    let ptr = allocator.allocate(layout).expect("failed to allocate");
    allocator.deallocate(ptr, layout);

    // Check regions have been combined and the free size is back at the
    // original first region size
    let region = allocator.get_region_first().expect("failed to get region");
    assert_eq!(region.size(), region_size);
    assert_eq!(region.get_used(), false);
}