Collections

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

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

If you need collections, a heap allocated implementation is not your onlyoption. You can also use fixed capacity collections; one such implementationcan 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 thecrate you can directly use it without declaring it as a dependency in yourCargo.toml file.

  1. #![feature(alloc)]
  3. extern crate alloc;
  5. use alloc::vec::Vec;

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

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

  1. // Bump pointer allocator implementation
  3. extern crate cortex_m;
  5. use core::alloc::GlobalAlloc;
  6. use core::ptr;
  8. use cortex_m::interrupt;
  10. // Bump pointer allocator for *single* core systems
  11. struct BumpPointerAlloc {
  12.     head: UnsafeCell<usize>,
  13.     end: usize,
  14. }
  16. unsafe impl Sync for BumpPointerAlloc {}
  18. unsafe impl GlobalAlloc for BumpPointerAlloc {
  19.     unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
  20.         // `interrupt::free` is a critical section that makes our allocator safe
  21.         // to use from within interrupts
  22.         interrupt::free(|_| {
  23.             let head = self.head.get();
  25.             let align = layout.align();
  26.             let res = *head % align;
  27.             let start = if res == 0 { *head } else { *head + align - res };
  28.             if start + align > self.end {
  29.                 // a null pointer signal an Out Of Memory condition
  30.                 ptr::null_mut()
  31.             } else {
  32.                 *head = start + align;
  33.                 start as *mut u8
  34.             }
  35.         })
  36.     }
  38.     unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
  39.         // this allocator never deallocates memory
  40.     }
  41. }
  43. // Declaration of the global memory allocator
  44. // NOTE the user must ensure that the memory region `[0x2000_0100, 0x2000_0200]`
  45. // is not used by other parts of the program
  46. #[global_allocator]
  47. static HEAP: BumpPointerAlloc = BumpPointerAlloc {
  48.     head: UnsafeCell::new(0x2000_0100),
  49.     end: 0x2000_0200,
  50. };

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

  1. #![feature(alloc_error_handler)]
  3. use cortex_m::asm;
  5. #[alloc_error_handler]
  6. fn on_oom(_layout: Layout) -> ! {
  7.     asm::bkpt();
  9.     loop {}
  10. }

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

  1. #[entry]
  2. fn main() -> ! {
  3.     let mut xs = Vec::new();
  5.     xs.push(42);
  6.     assert!(xs.pop(), Some(42));
  8.     loop {
  9.         // ..
  10.     }
  11. }

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

Using heapless

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

  1. extern crate heapless; // v0.4.x
  3. use heapless::Vec;
  4. use heapless::consts::*;
  6. #[entry]
  7. fn main() -> ! {
  8.     let mut xs: Vec<_, U8> = Vec::new();
  10.     xs.push(42).unwrap();
  11.     assert_eq!(xs.pop(), Some(42));
  12. }

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

First, you have to declare upfront the capacity of the collection. heaplesscollections never reallocate and have fixed capacities; this capacity is part ofthe type signature of the collection. In this case we have declared that xshas 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 theheapless collections have fixed capacity all operations that insert elementsinto the collection can potentially fail. The API reflects this problem byreturning a Result indicating whether the operation succeeded or not. Incontrast, alloc collections will reallocate themselves on the heap to increasetheir 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 allocatethe collection on the stack, but it's also possible to allocate the collectionon a static variable, or even on the heap (Box<Vec<, >>).

Trade-offs

Keep these in mind when choosing between heap allocated, relocatable collectionsand fixed capacity collections.

Out Of Memory and error handling

With heap allocations Out Of Memory is always a possibility and can occur inany place where a collection may need to grow: for example, allalloc::Vec.push invocations can potentially generate an OOM condition. Thussome operations can implicitly fail. Some alloc collections exposetry_reserve methods that let you check for potential OOM conditions whengrowing the collection but you need be proactive about using them.

If you exclusively use heapless collections and you don't use a memoryallocator for anything else then an OOM condition is impossible. Instead, you'llhave to deal with collections running out of capacity on a case by case basis.That is you'll have deal with all the Results returned by methods likeVec.push.

OOM failures can be harder to debug than say unwrap-ing on all Resultsreturned by heapless::Vec.push because the observed location of failure maynot match with the location of the cause of the problem. For example, evenvec.reserve(1) can trigger an OOM if the allocator is nearly exhausted becausesome other collection was leaking memory (memory leaks are possible in safeRust).

Memory usage

Reasoning about memory usage of heap allocated collections is hard because thecapacity of long lived collections can change at runtime. Some operations mayimplicitly reallocate the collection increasing its memory usage, and somecollections expose methods like shrinkto_fit that can potentially reduce thememory used by the collection — ultimately, it's up to the allocator to decidewhether to actually shrink the memory allocation or not. Additionally, theallocator may have to deal with memory fragmentation which can increase the_apparent memory usage.

On the other hand if you exclusively use fixed capacity collections, storemost of them in static variables and set a maximum size for the call stackthen the linker will detect if you try to use more memory than what's physicallyavailable.

Furthermore, fixed capacity collections allocated on the stack will be reportedby -Z emit-stack-sizes flag which means that tools that analyze stack usage(like stack-sizes) will include them in their analysis.

However, fixed capacity collections can not be shrunk which can result inlower load factors (the ratio between the size of the collection and itscapacity) than what relocatable collections can achieve.

Worst Case Execution Time (WCET)

If are building time sensitive applications or hard real time applications thenyou care, maybe a lot, about the worst case execution time of the differentparts of your program.

The alloc collections can reallocate so the WCET of operations that may growthe collection will also include the time it takes to reallocate the collection,which itself depends on the runtime capacity of the collection. This makes ithard to determine the WCET of, for example, the alloc::Vec.push operation asit depends on both the allocator being used and its runtime capacity.

On the other hand fixed capacity collections never reallocate so all operationshave a predictable execution time. For example, heapless::Vec.push executes inconstant time.

Ease of use

alloc requires setting up a global allocator whereas heapless does not.However, heapless requires you to pick the capacity of each collection thatyou instantiate.

The alloc API will be familiar to virtually every Rust developer. Theheapless API tries to closely mimic the alloc API but it will never beexactly the same due to its explicit error handling — some developers may feelthe explicit error handling is excessive or too cumbersome.