The Embedded Rust Book

Eventually you'll want to use dynamic data structures (AKA collections) in your program. std provides a set of common collections: Vec, String, HashMap, etc. All the collections implemented in std use a global dynamic memory allocator (AKA the heap).

As core is, by definition, free of memory allocations these implementations are not available there, but they can be found in the alloc crate that's shipped with the compiler.

If you need collections, a heap allocated implementation is not your only option. You can also use fixed capacity collections; one such implementation can be found in the heapless crate.

In this section, we'll explore and compare these two implementations.

Using

alloc

The alloc crate is shipped with the standard Rust distribution. To import the crate you can directly use it without declaring it as a dependency in your Cargo.toml file.

#![feature(alloc)]

extern crate alloc;

use alloc::vec::Vec;

To be able to use any collection you'll first need use the global_allocator attribute to declare the global allocator your program will use. It's required that the allocator you select implements the GlobalAlloc trait.

For completeness and to keep this section as self-contained as possible we'll implement a simple bump pointer allocator and use that as the global allocator. However, we strongly suggest you use a battle tested allocator from crates.io in your program instead of this allocator.

// Bump pointer allocator implementation

extern crate cortex_m;

use core::alloc::GlobalAlloc;

use core::ptr;

use cortex_m::interrupt;

// Bump pointer allocator for *single* core systems

struct BumpPointerAlloc {

head: UnsafeCell,

end: usize,

}

unsafe impl Sync for BumpPointerAlloc {}

unsafe impl GlobalAlloc for BumpPointerAlloc {

unsafe fn alloc(&self, layout: Layout) -> *mut u8 {

// `interrupt::free` is a critical section that makes our allocator safe

// to use from within interrupts

interrupt::free(|_| {

let head = self.head.get();

let size = layout.size();

let align = layout.align();

let align_mask = !(align - 1);

// move start up to the next alignment boundary

let start = (*head + align - 1) & align_mask;

if start + size > self.end {

// a null pointer signal an Out Of Memory condition

ptr::null_mut()

} else {

*head = start + size;

start as *mut u8

}

})

}

unsafe fn dealloc(&self, _: *mut u8, _: Layout) {

// this allocator never deallocates memory

}

}

// Declaration of the global memory allocator

// NOTE the user must ensure that the memory region `[0x2000_0100, 0x2000_0200]`

// is not used by other parts of the program

#[global_allocator]

static HEAP: BumpPointerAlloc = BumpPointerAlloc {

head: UnsafeCell::new(0x2000_0100),

end: 0x2000_0200,

};

Apart from selecting a global allocator the user will also have to define how Out Of Memory (OOM) errors are handled using the unstable alloc_error_handler attribute.

#![feature(alloc_error_handler)]

use cortex_m::asm;

#[alloc_error_handler]

fn on_oom(_layout: Layout) -> ! {

asm::bkpt();

loop {}

}

Once all that is in place, the user can finally use the collections in alloc.

#[entry]

fn main() -> ! {

let mut xs = Vec::new();

xs.push(42);

assert!(xs.pop(), Some(42));

loop {

// ..

}

}

If you have used the collections in the std crate then these will be familiar as they are exact same implementation.

Using

heapless

heapless requires no setup as its collections don't depend on a global memory allocator. Just use its collections and proceed to instantiate them:

extern crate heapless; // v0.4.x

use heapless::Vec;

use heapless::consts::*;

#[entry]

fn main() -> ! {

let mut xs: Vec<_, U8> = Vec::new();

xs.push(42).unwrap();

assert_eq!(xs.pop(), Some(42));

}

You'll note two differences between these collections and the ones in alloc.

First, you have to declare upfront the capacity of the collection. heapless collections never reallocate and have fixed capacities; this capacity is part of the type signature of the collection. In this case we have declared that xs has a capacity of 8 elements that is the vector can, at most, hold 8 elements. This is indicated by the U8 (see typenum) in the type signature.

Second, the push method, and many other methods, return a Result. Since the heapless collections have fixed capacity all operations that insert elements into the collection can potentially fail. The API reflects this problem by returning a Result indicating whether the operation succeeded or not. In contrast, alloc collections will reallocate themselves on the heap to increase their capacity.

As of version v0.4.x all heapless collections store all their elements inline. This means that an operation like let x = heapless::Vec::new(); will allocate the collection on the stack, but it's also possible to allocate the collection on a static variable, or even on the heap (Box>).

Trade-offs