Struct Stalloc

#[repr(C)]
pub struct Stalloc<const L: usize, const B: usize>
where
    Align<B>: Alignment,
{ /* private fields */ }

A fast first-fit memory allocator.

When you create an instance of this allocator, you pass in a value for L and B. L is the number of blocks, and B is the size of each block in bytes. The total size of this type comes out to L * B + 4 bytes, of which L * B can be used (4 bytes are needed to hold some metadata). B must be a power of two from 4 and 2^29, and L must be a number in the range 1..65536.

B represents the smallest unit of memory that the allocator can manage. If B == 16, then asking for 17 bytes will give you a 32 byte allocation (the amount is rounded up). The alignment of the allocator is always equal to B. For maximum efficiency, it is recommended to set B equal to the alignment of the type you expect to store the most of. For example, if you’re storing a lot of u64s, you should set B == 8.

Note that Stalloc cannot be used as a global allocator because it is not thread-safe. To switch out the global allocator, use SyncStalloc or UnsafeStalloc, which can be used concurrently.

Implementations

impl<const L: usize, const B: usize> Stalloc<L, B>

where Align<B>: Alignment,

pub const fn new() -> Self

Initializes a new empty Stalloc instance.

Examples

use stalloc::Stalloc;

let alloc = Stalloc::<200, 8>::new();

pub fn is_oom(&self) -> bool

Checks if the allocator is completely out of memory. If this is false, then you are guaranteed to be able to allocate a layout with a size and alignment of B bytes. This runs in O(1).

Examples

use stalloc::Stalloc;

let alloc = Stalloc::<200, 8>::new();
assert!(!alloc.is_oom());
let ptr = unsafe { alloc.allocate_blocks(200, 1).unwrap() };
assert!(alloc.is_oom());

pub fn is_empty(&self) -> bool

Checks if the allocator is empty. If this is true, then you are guaranteed to be able to allocate a layout with a size of B * L bytes and an alignment of B bytes. If this is false, then this is guaranteed to be impossible. This runs in O(1).

Examples

use stalloc::Stalloc;

let alloc = Stalloc::<60, 4>::new();
assert!(alloc.is_empty());

let ptr = unsafe { alloc.allocate_blocks(60, 1).unwrap() };
assert!(!alloc.is_empty());

unsafe { alloc.deallocate_blocks(ptr, 60) };
assert!(alloc.is_empty());

pub unsafe fn clear(&self)

Safety

Calling this function immediately invalidates all pointers into the allocator. Calling deallocate_blocks() with an invalidated pointer will result in the free list being corrupted.

Examples

use stalloc::Stalloc;

let alloc = Stalloc::<60, 4>::new();

let ptr1 = unsafe { alloc.allocate_blocks(20, 1) }.unwrap();
let ptr2 = unsafe { alloc.allocate_blocks(20, 1) }.unwrap();
let ptr3 = unsafe { alloc.allocate_blocks(20, 1) }.unwrap();

unsafe { alloc.clear() }; // invalidate all allocated pointers

assert!(alloc.is_empty());

Examples found in repository

examples/fast_vectors.rs (line 25)

fn main() {
	let start = Instant::now();
	for _ in 0..10_000_000 {
		let mut a = vec![];
		let mut b = vec![];
		for i in 0..10 {
			a.push(i);
			b.push(i);
		}

		mem::forget(a);
		mem::forget(b);

		// By clearing the global allocator, we can quickly drop both vectors together.
		// SAFETY: There are no more active allocations into `GLOBAL`.
		unsafe {
			GLOBAL.clear();
		}
	}

	println!("Elapsed: {}ms", start.elapsed().as_millis());
}

pub unsafe fn allocate_blocks( &self, size: usize, align: usize, ) -> Result<NonNull<u8>, AllocError>

Tries to allocate count blocks. If the allocation succeeds, a pointer is returned. This function never allocates more than necessary. Note that align is measured in units of B.

Safety

size must be nonzero, and align must be a power of 2 in the range 1..=2^29 / B.

Errors

Will return AllocError if the allocation was unsuccessful, in which case this function was a no-op.

Examples

use stalloc::Stalloc;

const BLOCK_SIZE: usize = 4;
let alloc = Stalloc::<10, BLOCK_SIZE>::new();

let ptr = unsafe { alloc.allocate_blocks(10, 1) }.unwrap();
unsafe { ptr.write_bytes(42, 10 * BLOCK_SIZE) };

assert!(alloc.is_oom());

pub unsafe fn deallocate_blocks(&self, ptr: NonNull<u8>, size: usize)

Deallocates a pointer. This function always succeeds.

Safety

ptr must point to an allocation, and size must be the number of blocks in the allocation. That is, size is always in 1..=L.

Examples

use stalloc::Stalloc;

let alloc = Stalloc::<100, 16>::new();

let ptr = unsafe { alloc.allocate_blocks(100, 1) }.unwrap();
assert!(alloc.is_oom());

unsafe { alloc.deallocate_blocks(ptr, 100) };
assert!(alloc.is_empty());

pub unsafe fn shrink_in_place( &self, ptr: NonNull<u8>, old_size: usize, new_size: usize, )

Shrinks the allocation. This function always succeeds and never reallocates.

Safety

ptr must point to a valid allocation of old_size blocks, and new_size must be in 1..old_size.

Examples

use stalloc::Stalloc;

let alloc = Stalloc::<100, 16>::new();

let ptr = unsafe { alloc.allocate_blocks(100, 1) }.unwrap();
assert!(alloc.is_oom());

// shrink the allocation from 100 to 90 blocks
unsafe { alloc.shrink_in_place(ptr, 100, 90) };
assert!(!alloc.is_oom());

pub unsafe fn grow_in_place( &self, ptr: NonNull<u8>, old_size: usize, new_size: usize, ) -> Result<(), AllocError>

Tries to grow the current allocation in-place. If that isn’t possible, this function is a no-op.

Safety

ptr must point to a valid allocation of old_size blocks. Also, new_size > old_size.

Errors

Will return AllocError if the grow was unsuccessful, in which case this function was a no-op.

Examples

use stalloc::Stalloc;

let alloc = Stalloc::<100, 16>::new();

let ptr = unsafe { alloc.allocate_blocks(25, 1) }.unwrap();
assert!(!alloc.is_oom());

// grow the allocation from 25 to 100 blocks
unsafe { alloc.grow_in_place(ptr, 25, 100) }.unwrap();
assert!(alloc.is_oom());

pub unsafe fn grow_up_to( &self, ptr: NonNull<u8>, old_size: usize, new_size: usize, ) -> usize

Tries to grow the current allocation in-place. If that isn’t possible, the allocator grows by as much as it is able to, and the new length of the allocation is returned. The new length is guaranteed to be in the range old_size..=new_size.

Safety

ptr must point to a valid allocation of old_size blocks. Also, new_size > old_size.

Examples

use stalloc::Stalloc;

let alloc1 = Stalloc::<7, 4>::new();
unsafe {
    let ptr = alloc1.allocate_blocks(3, 1).unwrap(); // allocate 3 blocks
    let new_size = alloc1.grow_up_to(ptr, 3, 9999); // try to grow to a ridiculous amount
    assert_eq!(new_size, 7); // can only grow up to 7
}

let alloc2 = Stalloc::<21, 16>::new();
unsafe {
    let ptr = alloc2.allocate_blocks(9, 1).unwrap(); // allocate 9 blocks
    let new_size = alloc2.grow_up_to(ptr, 9, 21);
    assert_eq!(new_size, 21); // grow was successful
}

impl<const L: usize, const B: usize> Stalloc<L, B>

where Align<B>: Alignment,

pub const fn chain<T>(self, next: &T) -> AllocChain<'_, Self, T>

where Self: Sized,

Creates a new AllocChain containing this allocator and next.

Trait Implementations

impl<const L: usize, const B: usize> ChainableAlloc for Stalloc<L, B>

where Align<B>: Alignment,

fn addr_in_bounds(&self, addr: usize) -> bool

Checks whether a certain address is contained within the allocator. This is called when using deallocate() and related functions in order to determine which allocator needs to free the pointer.

impl<const L: usize, const B: usize> Debug for Stalloc<L, B>

where Align<B>: Alignment,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const L: usize, const B: usize> Default for Stalloc<L, B>

where Align<B>: Alignment,

fn default() -> Self

Returns the “default value” for a type.