Crate teaspoon

Expand description

Teaspoon: an allocator for when all you have is a teaspoon of memory.

Teaspoon is a lightweight memory allocator designed for minimal overhead. It’s meant to be used in situations where you have very limited memory available, or when you want to allocate objects on the stack.

Teaspoon is optimized for low memory overhead first, and performance second.

This is a no-std and no-alloc crate, as such it does not interact with the operating system to reserve memory pages; the allocatable memory needs to be provided by you as an input to Teaspoon.

§Features

Small memory overhead: starting at 4 bytes per allocated object
Compatible with no_std environments
Support for the nightly Allocator API

§Quick start & examples

§Initialization

There are 3 variants of the allocator to choose from:

The size in the name (4KiB, 128KiB, 16MiB) refers to the maximum size for an individual allocated object, and the total memory that can be allocated may be greater than that. For example, with Teaspoon4KiB, you cannot allocate a 5000-byte object (because that exceeds the 4 KiB = 4096 byte limit), but you can allocate two 3000-byte objects.

Choosing the right variant is a matter of how much memory you have available, how much memory you’re willing to sacrifice for overhead, and performance. Smaller variants have smaller overheads. Note that the smaller variants may not necessarily be the faster. All the differences between the 3 allocator variants are described in Allocator limits.

Because Teaspoon does not interact with the operating system, you’ll need to initialize the allocator with some contiguous memory area that you already have. If you know the address, you can use one of Teaspoon::from_ptr, Teaspoon::from_ptr_size, Teaspoon::from_addr_size, like this:

use teaspoon::Teaspoon4KiB;
let spoon = unsafe { Teaspoon4KiB::<'static>::from_addr_size(0xdeadbeef, 1024) };

You can also construct the allocator from a byte slice. This can be useful for example to construct the allocator from an array on the stack:

use teaspoon::Teaspoon4KiB;
let mut memory = [0u8; 1024];
let spoon = Teaspoon4KiB::from(&mut memory);

You could also initialize the Teaspoon allocator from memory obtained from the operating system like this:

use std::alloc::GlobalAlloc;
use std::alloc::Layout;
use std::alloc::System;
use teaspoon::Teaspoon4KiB;

let size = 1024;
let ptr =
    unsafe { System.alloc(Layout::from_size_align(size, 4).expect("layout creation failed")) };
let spoon = unsafe { Teaspoon4KiB::from_ptr_size(ptr, size) };

Regardless of how you initialize the Teaspoon allocator, you have two choices for using it: using it as a global allocator for your entire Rust program, or using it through the new Allocator API (currently available on the nighly compiler only).

§Using as a global allocator

Teaspoon can be used as a custom global allocator via the #[global_allocator] attribute. Because #[global_allocator] requires a static item, it’s not possible to use Teaspoon objects directly, and instead lazy initialization is required. To aid with this, this crate provides a LazyTeaspoon type that can be used as follows:

Cargo.toml:

teaspoon = { version = "0.1", features = ["lazy"] }

main.rs:

use teaspoon::lazy::LazyTeaspoon4KiB;
use teaspoon::Teaspoon4KiB;

#[global_allocator]
static SPOON: LazyTeaspoon4KiB = LazyTeaspoon4KiB::new(|| {
    static mut MEMORY: [u8; 1024] = [0u8; 1024];
    // SAFETY: This closure is called only once, therefore `MEMORY` is entirely owned by
    // this `Teaspoon4KiB`, and no other reference can be created.
    Teaspoon4KiB::from(unsafe { &mut MEMORY })
});

LazyTeaspoon is initialized on first use by calling the initialization function passed to new.

LazyTeaspoon is a simple wrapper around [spin::Lazy] (which is a no_std equivalent to std::sync::LazyLock) that implements the GlobalAlloc and [Allocator] traits. There’s nothing too special about it–you can write your own custom wrapper if you need to.

§Using via the Allocator API

Teaspoon can be used as a custom allocator to be passed to the “new_in” methods of various container types (such as Box::new_in, Vec::new_in, …). Because the Allocator API is currently experimental, it is only available in the Rust nightly compiler, and with #![feature(allocator_api)]. It can be used as follows:

Cargo.toml:

teaspoon = { version = "0.1", features = ["allocator-api"] }

main.rs:

#![feature(allocator_api)]

use teaspoon::Teaspoon4KiB;

let mut memory = [0u8; 1024];
let spoon = Teaspoon4KiB::from(&mut memory);

let mut vec = Vec::<i32, _>::new_in(&spoon);
vec.push(1);
vec.push(2);
vec.push(3);

§Allocator limits

Arena Overhead: amount of memory that is reserved for Teaspoon internal structures. This amount of memory is always used by Teaspoon, even when no objects are allocated.
Object Overhead: amount of extra memory that is allocated for every allocated object (with the exception of zero-sized types, which have no overhead).
Minimum Object Size: minimum size that is always allocated for every object (with the exception of zero-sized types). If an allocation requests a size less than the minimum size, it is rounded up to the minimum size.
Maximum Object Size: maximum size that can be allocated to a single object. Allocations larger than the maximum size always fail. This does not mean that all allocations up to this maximum size will succeed: factors like available memory and memory fragmentation may result in an actual lower limit at runtime.
Maximum Total Memory^{[note 1]}: maximum total memory that can be addressed by a Teaspoon object.

	Arena Overhead	Object Overhead	Minimum Object Size	Maximum Object Size	Maximum Total Memory^{[note 1]}
`Teaspoon4KiB`	4 bytes	4 bytes	4 bytes	4096 bytes (4 KiB)	8192 bytes (8 KiB)
`Teaspoon128KiB`	4 bytes	6 bytes	2 bytes	131072 bytes (128 KiB)	131072 bytes (128 KiB)
`Teaspoon16MiB`	8 bytes	8 bytes	8 bytes	16777216 bytes (16 MiB)	16777216 bytes (16 MiB)

[note 1]: this restriction may be lifted in a future version of this crate.

§Internal details

Teaspoon is a compact memory allocator using a doubly-linked list to track allocated objects, and a spin lock to ensure thread safety.

The “Object Overhead” listed in Allocator limits is used to store the previous/next pointers of the linked list, and the size of the object. The “Arena Overhead” is used to store the head/tail pointers of the linked list.

§Cargo feature flags

allocator-api: enables the implementation of the core::alloc::Allocator trait (requires a nightly compiler).
lazy: enables the LazyTeaspoon type along with its sized variants.

Structs§

Sizing4KiB: Marker trait for Teaspoon that supports allocating objects up to 4 KiB.
Sizing16MiB: Marker trait for Teaspoon that supports allocating objects up to 16 MiB.
Sizing128KiB: Marker trait for Teaspoon that supports allocating objects up to 128 KiB.
Teaspoon: The Teaspoon allocator.
Usage: Memory usage information.

Traits§

Sizing: Trait to define overhead and sizing limits on Teaspoon variants.

Type Aliases§

Teaspoon4KiB: Allocator that supports allocating objects up to 4 KiB.
Teaspoon16MiB: Allocator that supports allocating objects up to 16 MiB.
Teaspoon128KiB: Allocator that supports allocating objects up to 128 KiB.

Crate teaspoonCopy item path