| <!DOCTYPE HTML> |
| <html lang="en" class="light sidebar-visible" dir="ltr"> |
| <head> |
| <!-- Book generated using mdBook --> |
| <meta charset="UTF-8"> |
| <title>Collections - The Embedded Rust Book</title> |
| |
| |
| <!-- Custom HTML head --> |
| |
| <meta name="description" content=""> |
| <meta name="viewport" content="width=device-width, initial-scale=1"> |
| <meta name="theme-color" content="#ffffff"> |
| |
| <link rel="icon" href="../favicon.svg"> |
| <link rel="shortcut icon" href="../favicon.png"> |
| <link rel="stylesheet" href="../css/variables.css"> |
| <link rel="stylesheet" href="../css/general.css"> |
| <link rel="stylesheet" href="../css/chrome.css"> |
| <link rel="stylesheet" href="../css/print.css" media="print"> |
| |
| <!-- Fonts --> |
| <link rel="stylesheet" href="../FontAwesome/css/font-awesome.css"> |
| <link rel="stylesheet" href="../fonts/fonts.css"> |
| |
| <!-- Highlight.js Stylesheets --> |
| <link rel="stylesheet" id="highlight-css" href="../highlight.css"> |
| <link rel="stylesheet" id="tomorrow-night-css" href="../tomorrow-night.css"> |
| <link rel="stylesheet" id="ayu-highlight-css" href="../ayu-highlight.css"> |
| |
| <!-- Custom theme stylesheets --> |
| |
| |
| <!-- Provide site root and default themes to javascript --> |
| <script> |
| const path_to_root = "../"; |
| const default_light_theme = "light"; |
| const default_dark_theme = "navy"; |
| </script> |
| <!-- Start loading toc.js asap --> |
| <script src="../toc.js"></script> |
| </head> |
| <body> |
| <div id="mdbook-help-container"> |
| <div id="mdbook-help-popup"> |
| <h2 class="mdbook-help-title">Keyboard shortcuts</h2> |
| <div> |
| <p>Press <kbd>←</kbd> or <kbd>→</kbd> to navigate between chapters</p> |
| <p>Press <kbd>S</kbd> or <kbd>/</kbd> to search in the book</p> |
| <p>Press <kbd>?</kbd> to show this help</p> |
| <p>Press <kbd>Esc</kbd> to hide this help</p> |
| </div> |
| </div> |
| </div> |
| <div id="body-container"> |
| <!-- Work around some values being stored in localStorage wrapped in quotes --> |
| <script> |
| try { |
| let theme = localStorage.getItem('mdbook-theme'); |
| let sidebar = localStorage.getItem('mdbook-sidebar'); |
| |
| if (theme.startsWith('"') && theme.endsWith('"')) { |
| localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1)); |
| } |
| |
| if (sidebar.startsWith('"') && sidebar.endsWith('"')) { |
| localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1)); |
| } |
| } catch (e) { } |
| </script> |
| |
| <!-- Set the theme before any content is loaded, prevents flash --> |
| <script> |
| const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme; |
| let theme; |
| try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { } |
| if (theme === null || theme === undefined) { theme = default_theme; } |
| const html = document.documentElement; |
| html.classList.remove('light') |
| html.classList.add(theme); |
| html.classList.add("js"); |
| </script> |
| |
| <input type="checkbox" id="sidebar-toggle-anchor" class="hidden"> |
| |
| <!-- Hide / unhide sidebar before it is displayed --> |
| <script> |
| let sidebar = null; |
| const sidebar_toggle = document.getElementById("sidebar-toggle-anchor"); |
| if (document.body.clientWidth >= 1080) { |
| try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { } |
| sidebar = sidebar || 'visible'; |
| } else { |
| sidebar = 'hidden'; |
| } |
| sidebar_toggle.checked = sidebar === 'visible'; |
| html.classList.remove('sidebar-visible'); |
| html.classList.add("sidebar-" + sidebar); |
| </script> |
| |
| <nav id="sidebar" class="sidebar" aria-label="Table of contents"> |
| <!-- populated by js --> |
| <mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox> |
| <noscript> |
| <iframe class="sidebar-iframe-outer" src="../toc.html"></iframe> |
| </noscript> |
| <div id="sidebar-resize-handle" class="sidebar-resize-handle"> |
| <div class="sidebar-resize-indicator"></div> |
| </div> |
| </nav> |
| |
| <div id="page-wrapper" class="page-wrapper"> |
| |
| <div class="page"> |
| <div id="menu-bar-hover-placeholder"></div> |
| <div id="menu-bar" class="menu-bar sticky"> |
| <div class="left-buttons"> |
| <label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar"> |
| <i class="fa fa-bars"></i> |
| </label> |
| <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list"> |
| <i class="fa fa-paint-brush"></i> |
| </button> |
| <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu"> |
| <li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li> |
| <li role="none"><button role="menuitem" class="theme" id="light">Light</button></li> |
| <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li> |
| <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li> |
| <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li> |
| <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li> |
| </ul> |
| <button id="search-toggle" class="icon-button" type="button" title="Search (`/`)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="/ s" aria-controls="searchbar"> |
| <i class="fa fa-search"></i> |
| </button> |
| </div> |
| |
| <h1 class="menu-title">The Embedded Rust Book</h1> |
| |
| <div class="right-buttons"> |
| <a href="../print.html" title="Print this book" aria-label="Print this book"> |
| <i id="print-button" class="fa fa-print"></i> |
| </a> |
| <a href="https://github.com/rust-embedded/book" title="Git repository" aria-label="Git repository"> |
| <i id="git-repository-button" class="fa fa-github"></i> |
| </a> |
| |
| </div> |
| </div> |
| |
| <div id="search-wrapper" class="hidden"> |
| <form id="searchbar-outer" class="searchbar-outer"> |
| <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header"> |
| </form> |
| <div id="searchresults-outer" class="searchresults-outer hidden"> |
| <div id="searchresults-header" class="searchresults-header"></div> |
| <ul id="searchresults"> |
| </ul> |
| </div> |
| </div> |
| |
| <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM --> |
| <script> |
| document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible'); |
| document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible'); |
| Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) { |
| link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1); |
| }); |
| </script> |
| |
| <div id="content" class="content"> |
| <main> |
| <h1 id="collections"><a class="header" href="#collections">Collections</a></h1> |
| <p>Eventually you'll want to use dynamic data structures (AKA collections) in your |
| program. <code>std</code> provides a set of common collections: <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html"><code>Vec</code></a>, <a href="https://doc.rust-lang.org/std/string/struct.String.html"><code>String</code></a>, |
| <a href="https://doc.rust-lang.org/std/collections/struct.HashMap.html"><code>HashMap</code></a>, etc. All the collections implemented in <code>std</code> use a global dynamic |
| memory allocator (AKA the heap).</p> |
| <p>As <code>core</code> is, by definition, free of memory allocations these implementations |
| are not available there, but they can be found in the <code>alloc</code> crate |
| that's shipped with the compiler.</p> |
| <p>If you need collections, a heap allocated implementation is not your only |
| option. You can also use <em>fixed capacity</em> collections; one such implementation |
| can be found in the <a href="https://crates.io/crates/heapless"><code>heapless</code></a> crate.</p> |
| <p>In this section, we'll explore and compare these two implementations.</p> |
| <h2 id="using-alloc"><a class="header" href="#using-alloc">Using <code>alloc</code></a></h2> |
| <p>The <code>alloc</code> crate is shipped with the standard Rust distribution. To import the |
| crate you can directly <code>use</code> it <em>without</em> declaring it as a dependency in your |
| <code>Cargo.toml</code> file.</p> |
| <pre><code class="language-rust ignore">#![feature(alloc)] |
| |
| extern crate alloc; |
| |
| use alloc::vec::Vec;</code></pre> |
| <p>To be able to use any collection you'll first need use the <code>global_allocator</code> |
| attribute to declare the global allocator your program will use. It's required |
| that the allocator you select implements the <a href="https://doc.rust-lang.org/core/alloc/trait.GlobalAlloc.html"><code>GlobalAlloc</code></a> trait.</p> |
| <p>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 <em>strongly</em> suggest you use a battle tested allocator from crates.io |
| in your program instead of this allocator.</p> |
| <pre><code class="language-rust ignore">// Bump pointer allocator implementation |
| |
| use core::alloc::{GlobalAlloc, Layout}; |
| use core::cell::UnsafeCell; |
| use core::ptr; |
| |
| use cortex_m::interrupt; |
| |
| // Bump pointer allocator for *single* core systems |
| struct BumpPointerAlloc { |
| head: UnsafeCell<usize>, |
| 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, |
| };</code></pre> |
| <p>Apart from selecting a global allocator the user will also have to define how |
| Out Of Memory (OOM) errors are handled using the <em>unstable</em> |
| <code>alloc_error_handler</code> attribute.</p> |
| <pre><code class="language-rust ignore">#![feature(alloc_error_handler)] |
| |
| use cortex_m::asm; |
| |
| #[alloc_error_handler] |
| fn on_oom(_layout: Layout) -> ! { |
| asm::bkpt(); |
| |
| loop {} |
| }</code></pre> |
| <p>Once all that is in place, the user can finally use the collections in <code>alloc</code>.</p> |
| <pre><code class="language-rust ignore">#[entry] |
| fn main() -> ! { |
| let mut xs = Vec::new(); |
| |
| xs.push(42); |
| assert!(xs.pop(), Some(42)); |
| |
| loop { |
| // .. |
| } |
| }</code></pre> |
| <p>If you have used the collections in the <code>std</code> crate then these will be familiar |
| as they are exact same implementation.</p> |
| <h2 id="using-heapless"><a class="header" href="#using-heapless">Using <code>heapless</code></a></h2> |
| <p><code>heapless</code> requires no setup as its collections don't depend on a global memory |
| allocator. Just <code>use</code> its collections and proceed to instantiate them:</p> |
| <pre><code class="language-rust ignore">// heapless version: 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)); |
| loop {} |
| }</code></pre> |
| <p>You'll note two differences between these collections and the ones in <code>alloc</code>.</p> |
| <p>First, you have to declare upfront the capacity of the collection. <code>heapless</code> |
| 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 <code>xs</code> |
| has a capacity of 8 elements that is the vector can, at most, hold 8 elements. |
| This is indicated by the <code>U8</code> (see <a href="https://crates.io/crates/typenum"><code>typenum</code></a>) in the type signature.</p> |
| <p>Second, the <code>push</code> method, and many other methods, return a <code>Result</code>. Since the |
| <code>heapless</code> collections have fixed capacity all operations that insert elements |
| into the collection can potentially fail. The API reflects this problem by |
| returning a <code>Result</code> indicating whether the operation succeeded or not. In |
| contrast, <code>alloc</code> collections will reallocate themselves on the heap to increase |
| their capacity.</p> |
| <p>As of version v0.4.x all <code>heapless</code> collections store all their elements inline. |
| This means that an operation like <code>let x = heapless::Vec::new();</code> will allocate |
| the collection on the stack, but it's also possible to allocate the collection |
| on a <code>static</code> variable, or even on the heap (<code>Box<Vec<_, _>></code>).</p> |
| <h2 id="trade-offs"><a class="header" href="#trade-offs">Trade-offs</a></h2> |
| <p>Keep these in mind when choosing between heap allocated, relocatable collections |
| and fixed capacity collections.</p> |
| <h3 id="out-of-memory-and-error-handling"><a class="header" href="#out-of-memory-and-error-handling">Out Of Memory and error handling</a></h3> |
| <p>With heap allocations Out Of Memory is always a possibility and can occur in |
| any place where a collection may need to grow: for example, all |
| <code>alloc::Vec.push</code> invocations can potentially generate an OOM condition. Thus |
| some operations can <em>implicitly</em> fail. Some <code>alloc</code> collections expose |
| <code>try_reserve</code> methods that let you check for potential OOM conditions when |
| growing the collection but you need be proactive about using them.</p> |
| <p>If you exclusively use <code>heapless</code> collections and you don't use a memory |
| allocator for anything else then an OOM condition is impossible. Instead, you'll |
| have to deal with collections running out of capacity on a case by case basis. |
| That is you'll have deal with <em>all</em> the <code>Result</code>s returned by methods like |
| <code>Vec.push</code>.</p> |
| <p>OOM failures can be harder to debug than say <code>unwrap</code>-ing on all <code>Result</code>s |
| returned by <code>heapless::Vec.push</code> because the observed location of failure may |
| <em>not</em> match with the location of the cause of the problem. For example, even |
| <code>vec.reserve(1)</code> can trigger an OOM if the allocator is nearly exhausted because |
| some other collection was leaking memory (memory leaks are possible in safe |
| Rust).</p> |
| <h3 id="memory-usage"><a class="header" href="#memory-usage">Memory usage</a></h3> |
| <p>Reasoning about memory usage of heap allocated collections is hard because the |
| capacity of long lived collections can change at runtime. Some operations may |
| implicitly reallocate the collection increasing its memory usage, and some |
| collections expose methods like <code>shrink_to_fit</code> that can potentially reduce the |
| memory used by the collection -- ultimately, it's up to the allocator to decide |
| whether to actually shrink the memory allocation or not. Additionally, the |
| allocator may have to deal with memory fragmentation which can increase the |
| <em>apparent</em> memory usage.</p> |
| <p>On the other hand if you exclusively use fixed capacity collections, store |
| most of them in <code>static</code> variables and set a maximum size for the call stack |
| then the linker will detect if you try to use more memory than what's physically |
| available.</p> |
| <p>Furthermore, fixed capacity collections allocated on the stack will be reported |
| by <a href="https://doc.rust-lang.org/beta/unstable-book/compiler-flags/emit-stack-sizes.html"><code>-Z emit-stack-sizes</code></a> flag which means that tools that analyze stack usage |
| (like <a href="https://crates.io/crates/stack-sizes"><code>stack-sizes</code></a>) will include them in their analysis.</p> |
| <p>However, fixed capacity collections can <em>not</em> be shrunk which can result in |
| lower load factors (the ratio between the size of the collection and its |
| capacity) than what relocatable collections can achieve.</p> |
| <h3 id="worst-case-execution-time-wcet"><a class="header" href="#worst-case-execution-time-wcet">Worst Case Execution Time (WCET)</a></h3> |
| <p>If you are building time sensitive applications or hard real time applications |
| then you care, maybe a lot, about the worst case execution time of the different |
| parts of your program.</p> |
| <p>The <code>alloc</code> collections can reallocate so the WCET of operations that may grow |
| the collection will also include the time it takes to reallocate the collection, |
| which itself depends on the <em>runtime</em> capacity of the collection. This makes it |
| hard to determine the WCET of, for example, the <code>alloc::Vec.push</code> operation as |
| it depends on both the allocator being used and its runtime capacity.</p> |
| <p>On the other hand fixed capacity collections never reallocate so all operations |
| have a predictable execution time. For example, <code>heapless::Vec.push</code> executes in |
| constant time.</p> |
| <h3 id="ease-of-use"><a class="header" href="#ease-of-use">Ease of use</a></h3> |
| <p><code>alloc</code> requires setting up a global allocator whereas <code>heapless</code> does not. |
| However, <code>heapless</code> requires you to pick the capacity of each collection that |
| you instantiate.</p> |
| <p>The <code>alloc</code> API will be familiar to virtually every Rust developer. The |
| <code>heapless</code> API tries to closely mimic the <code>alloc</code> API but it will never be |
| exactly the same due to its explicit error handling -- some developers may feel |
| the explicit error handling is excessive or too cumbersome.</p> |
| |
| </main> |
| |
| <nav class="nav-wrapper" aria-label="Page navigation"> |
| <!-- Mobile navigation buttons --> |
| <a rel="prev" href="../concurrency/index.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left"> |
| <i class="fa fa-angle-left"></i> |
| </a> |
| |
| <a rel="next prefetch" href="../design-patterns/index.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right"> |
| <i class="fa fa-angle-right"></i> |
| </a> |
| |
| <div style="clear: both"></div> |
| </nav> |
| </div> |
| </div> |
| |
| <nav class="nav-wide-wrapper" aria-label="Page navigation"> |
| <a rel="prev" href="../concurrency/index.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left"> |
| <i class="fa fa-angle-left"></i> |
| </a> |
| |
| <a rel="next prefetch" href="../design-patterns/index.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right"> |
| <i class="fa fa-angle-right"></i> |
| </a> |
| </nav> |
| |
| </div> |
| |
| |
| |
| |
| <script> |
| window.playground_copyable = true; |
| </script> |
| |
| |
| <script src="../elasticlunr.min.js"></script> |
| <script src="../mark.min.js"></script> |
| <script src="../searcher.js"></script> |
| |
| <script src="../clipboard.min.js"></script> |
| <script src="../highlight.js"></script> |
| <script src="../book.js"></script> |
| |
| <!-- Custom JS scripts --> |
| |
| |
| </div> |
| </body> |
| </html> |
