rust-embedded / embedded-alloc Goto Github PK

View Code? Open in Web Editor NEW

267.0 20.0 52.0 111 KB

A heap allocator for embedded systems

License: Apache License 2.0

Rust 97.47% RPC 2.53%

rust no-std arm cortex-m microcontroller allocator

embedded-alloc's Introduction

- Documentation - Change log

`embedded-alloc`

A heap allocator for embedded systems.

Note that using this as your global allocator requires Rust 1.68 or later. (With earlier versions, you need the unstable feature #![feature(default_alloc_error_handler)])

This project is developed and maintained by the libs team.

Example

Starting with Rust 1.68, this crate can be used as a global allocator on stable Rust:

#![no_std]
#![no_main]

extern crate alloc;

use cortex_m_rt::entry;
use embedded_alloc::LlffHeap as Heap;

#[global_allocator]
static HEAP: Heap = Heap::empty();

#[entry]
fn main() -> ! {
    // Initialize the allocator BEFORE you use it
    {
        use core::mem::MaybeUninit;
        const HEAP_SIZE: usize = 1024;
        static mut HEAP_MEM: [MaybeUninit<u8>; HEAP_SIZE] = [MaybeUninit::uninit(); HEAP_SIZE];
        unsafe { HEAP.init(HEAP_MEM.as_ptr() as usize, HEAP_SIZE) }
    }

    // now the allocator is ready types like Box, Vec can be used.

    loop { /* .. */ }
}

For a full usage example, see examples/global_alloc.rs.

For this to work, an implementation of critical-section must be provided.

For simple use cases with Cortex-M CPUs you may enable the critical-section-single-core feature in the cortex-m crate. Please refer to the documentation of critical-section for further guidance.

Features

There are two heaps available to use:

llff: Provides LlffHeap, a Linked List First Fit heap.
tlsf: Provides TlsfHeap, a Two-Level Segregated Fit heap.

The best heap to use will depend on your application, see #78 for more discussion.

License

Licensed under either of

Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Code of Conduct

Contribution to this crate is organized under the terms of the Rust Code of Conduct, the maintainer of this crate, the libs team, promises to intervene to uphold that code of conduct.

embedded-alloc's People

Contributors

Stargazers

Watchers

embedded-alloc's Issues

Passing argument to init - wrong example?

In the example it says

unsafe { ALLOCATOR.init(_heap_start, _heap_end - _heap_start) }

As the linker gives you symbols, the address of which is the address you need (rather than the value itself), I think this should be

unsafe { ALLOCATOR.init(_heap_start as *mut usize as usize, (_heap_end as *mut usize as usize) - (_heap_start as *mut usize as usize) }

Or, you could change the API to take &mut T, and perform the calculations internally. This is what the r0 crate does.

error[E0015]: calls in constant functions are limited to constant functions

rustc 1.50.0-nightly (7efc097c4 2020-12-12)

cargo build

   Compiling alloc-cortex-m v0.4.0 (/home/jacob/git/alloc-cortex-m)

Error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants
  --> src/lib.rs:29:43
   |
29 |             heap: Mutex::new(RefCell::new(Heap::empty())),
   |                                           ^^^^^^^^^^^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0015`.
error: could not compile `alloc-cortex-m`

This fixes the error, but I'm not sure if this follows the original intent:

diff --git a/src/lib.rs b/src/lib.rs
index 56d2305..338aa0a 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -24,7 +24,7 @@ impl CortexMHeap {
     ///
     /// You must initialize this heap using the
     /// [`init`](struct.CortexMHeap.html#method.init) method before using the allocator.
-    pub const fn empty() -> CortexMHeap {
+    pub fn empty() -> CortexMHeap {
         CortexMHeap {
             heap: Mutex::new(RefCell::new(Heap::empty())),
         }

Heap length is end - start

The linked list allocator crate defines the heap as [start, start + size)

fn init() calculates size as end - start - 1, which means the heap is [start, end - 1), or one byte shorter than it need be. Size should just be end - start. That's a bug on my part (but at least it's a safe bug).

The comments say the heap size is end - start + 1, which is also wrong. That would mean we included the end byte.

Alloc -> AllocRef

Please update to linked_list_allocator = "0.6.6"

see. linked-list-allocator#20

Use OOM lang item

rust-lang/rust#50144 was merged, and Alloc/GlobalAlloc::oom has been replaced by a language item.

alloc-cortex-m now fails to build, error language item required, but not found: 'oom'

The latest version of linked_list_allocator removes OOM functions (rust-osdev/linked-list-allocator@f0de36d).

I'm afraid I don't understand enough about the change to suggest a fix :(

Make a new release on crates.io

When using the latest version from crates.io, I experience this issue: #28
Luckily this has been fixed, but this fix has not yet been released.

Is there anything holding the release back?
So far I've been using this repo as a git dependency and everything seems to work ok.

This crate should be flagged as single-core usage only

cortex-m is imported with critical-section-single-core, which makes it safe for use only in single-core systems.

Just disabling interrupts, as the implementations for critical-section-single-core and cortex-m::interrupt::free do, does not guarantee multi-core safety.

As a result this safety constraint should be documented somewhere.

Possible Broken Dependency: linked_list_allocator

Trying to build on OSx 10.15.3. With the following Rust & Cargo versions.

master* ❯ rustc --version                                                                                                                                                                                                12:12:47
rustc 1.43.0-nightly (c20d7eecb 2020-03-11)
master* ❯ cargo --version                                                                                                                                                                                                12:17:34
cargo 1.43.0-nightly (bda50510d 2020-03-02)

The following error occurs when trying to envoke cargo build.

error[E0053]: method `alloc` has an incompatible type for trait
   --> /Users/avlec/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.6.6/src/lib.rs:133:5
    |
133 |     unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected normal fn, found unsafe fn
    |
    = note: expected fn pointer `fn(&mut Heap, core::alloc::Layout) -> core::result::Result<(core::ptr::NonNull<u8>, usize), _>`
               found fn pointer `unsafe fn(&mut Heap, core::alloc::Layout) -> core::result::Result<core::ptr::NonNull<u8>, _>`

This is verified an issue with the version of linked_list_allocator, as building with the same environment on 0.6.6 yields the same error. It is to note that this error is from just building linked_list_allocator independently from alloc-cortex-m.

~/Downloads/linked-list-allocator-0b7fdddd067448327a3f6ad9d2b39045a2b3f922 ❯ cargo build                                                                                                                                             13:51:13
    Updating crates.io index
  Downloaded spin v0.5.2
   Compiling spin v0.5.2
   Compiling linked_list_allocator v0.6.6 (/Users/avlec/Downloads/linked-list-allocator-0b7fdddd067448327a3f6ad9d2b39045a2b3f922)
error[E0053]: method `alloc` has an incompatible type for trait
   --> src/lib.rs:133:5
    |
133 |     unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected normal fn, found unsafe fn
    |
    = note: expected fn pointer `fn(&mut Heap, core::alloc::Layout) -> core::result::Result<(core::ptr::NonNull<u8>, usize), _>`
               found fn pointer `unsafe fn(&mut Heap, core::alloc::Layout) -> core::result::Result<core::ptr::NonNull<u8>, _>`

Proposed solution is to update the linked_list_allocator dependency to 0.8.0 minimum, as this is the most recent version that successfully builds.

CI Failure

Scheduled CI run failed. Details:
https://github.com/rust-embedded/alloc-cortex-m/actions/runs/1200536155

Can not build for STM32 - undefined symbol critical section

As I am new to embedded, it could be that I am just missing something.
I am following the STM32F3DISCOVERY (https://docs.rust-embedded.org/book/).
The allocator example in the cortex_m_quickstart template is working fine using the 0.4.2 version of alloc-cortex-m and I can use e.g. ndarray.
When I test the example of the current version 0.5.0 of embedded_alloc it can't find the symbol critical_section.

Do you know what I need to change to make it run?

error: linking with `rust-lld` failed: exit status: 1
          rust-lld: error: undefined symbol: _critical_section_1_0_acquire
          >>> referenced by lib.rs:180 (/Users/aicse/.cargo/registry/src/index.crates.io-6f17d22bba15001f/critical-section-1.1.1/src/lib.rs:180)
          >>>               embedded_alloc-3c639d8a5411f8c8.embedded_alloc.77b68f61-cgu.5.rcgu.o:(critical_section::with::hdf8f1ccb073a5751) in archive /Users/aicse/Development/micro-layer-test/target/thumbv7em-none-eabihf/debug/deps/libembedded_alloc-3c639d8a5411f8c8.rlib
          
          rust-lld: error: undefined symbol: _critical_section_1_0_release
          >>> referenced by lib.rs:197 (/Users/aicse/.cargo/registry/src/index.crates.io-6f17d22bba15001f/critical-section-1.1.1/src/lib.rs:197)
          
error: could not compile `micro-layer-test` (bin "micro-layer-test") due to previous error

Release?

The released version of this crate is broken due to #40 (which was caused by a breaking change in a semver-minor release of linked-list-allocator.)

This means builds using this crate are broken, including cortex-m-quickstart.

Could we have a new release?

Build is failing on thumbv6

Caused by rust-osdev/linked-list-allocator#48

Is there a way to make the heap size configurable?

I am using embedded-alloc in my library. I would like the users of my library to be able to configure the heap size according to their platform at compile time. Is there a way to do that?

Does not build on latest nightly

When compiling this crate with the latest nightly, the following error occurs:

error[E0635]: unknown feature `const_unsafe_cell_new`
  --> /home/philipp/.cargo/registry/src/github.com-1ecc6299db9ec823/cortex-m-0.1.7/src/lib.rs:16:12
   |
16 | #![feature(const_unsafe_cell_new)]
   |            ^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

So the problem seems to be that this crate still uses the very old version 0.1.7 of cortex-m.

add example that proves extern "C" malloc and free

Sync with latest cortex-m version

It's not really a bug, but I can't do this synchronization. There is currently something that I did not understand in the functioning of rust

I tried to replace init() with:

use core::borrow::BorrowMut;
use core::ops::DerefMut;
use cortex_m::interrupt::Mutex;
use linked_list_allocator::Heap;
// ...
pub struct CortexMHeap {
    heap: Mutex<Heap>,
}
// ...

    pub unsafe fn init(&self, start_addr: usize, size: usize) {
        cortex_m::interrupt::free(|cs| {
               self.heap
                    .borrow(cs)
                    .borrow_mut()
                    .deref_mut()
                    .init(start_addr, size);
            });
    }
}

but answer is:

error[E0596]: cannot borrow data in a `&` reference as mutable
   --> src/lib.rs:103:17
    |
103 | /                 self.heap
104 | |                     .borrow(cs)
105 | |                     .borrow_mut()
106 | |                     .deref_mut()
    | |________________________________^ cannot borrow as mutable

Heap allocation considerations for embedded systems

I am a proponent of using a heap on embedded systems. I think there is a lot of unnecessary fear about it. That being said, I also think it needs to be very carefully considered what type of allocator is appropriate. I do not think the currently used linked_list_allocator is appropriate.

I've given this a lot of thought in the past (doesn't mean I'm not off-base). I think, in general, the primary requirement must be that the maximum heap memory usage must be bounded and deterministic even at the expense of memory efficiency. In other words, the "high water mark" of heap memory usage should be asymptotic over time. To achieve this, I believe it's correct to say that External Fragmentation must be prohibited.

It is my understanding that this can be achieved with Simple Segregated Storage. More specifically, an array of free lists where each list is a fixed-width bin of chunks. An object is allocated from the "narrowest" bin in which it fits. If that bin's free list is empty, it get's another block and extends the free list into this new block. Blocks are never released, chunks are never split/coalesced. I believe that this method (while not being especially memory efficient) does provide that asymptotic max usage by eliminating external fragmentation.

Perhaps the japaric/tlsf allocator (which at it's core uses segregated storage) would be a better fit.

I'm hoping to start a discussion here and look forward to reading any responses.

Get undefined reference to `debug_lower_hex` when using alloc crate

I've gotten code using core to run on the arc-elf32 target using rustc_codegen_gcc (as discussed in a Rust forum post)
I'm attempting to link C code which calls a Rust library that allocates on the heap by running arc-elf32-gcc lib.o example.c but am getting an undefined reference to core[47ee6e850c258048]::fmt::Formatter>::debug_lower_hex
The rust code successfully compiles using rustc example.rs --emit=obj -o lib.o --crate-type=lib -O
If I instead compile with --crate-type=cdylib or dylib I get dropping unsupported crate type cdylib for target

If I compile with --crate-type=staticlib then I get

error: no global memory allocator found but one is required; link to std or add `#[global_allocator]` to a static item that implements the GlobalAlloc trait
error: `#[panic_handler]` function required, but not found

After implementing a global memory allocator by following embedded-alloc and specifying a panic handler similar to global_alloc.rs, I still get an undefined reference to debug_lower_hex.

code

// example.rs which becomes lib.o
#![no_std]

extern crate alloc;
use alloc::vec::Vec;

#[no_mangle]
pub extern "C" fn rust() -> i32 {
    let y = 42;
    let mut vec = Vec::new();
    vec.push(y);
    vec.pop().unwrap()
}

// example.c
#include <stdint.h>
#include <stdarg.h>

int32_t rust(void);

int main()
{
    printf("from rust get value %d", rust());
}

full error output

/opt/arc/lib/gcc/arc-elf32/10.2.0/../../../../arc-elf32/bin/ld: /opt/arc/lib/gcc/arc-elf32/10.2.0/../../../../arc-elf32/bin/ld: DWARF error: can't find .debug_ranges section.
src/lib.o: in function `_RNvXsP_NtCs6aT7ng1d0qi_4core3fmtRjNtB5_5Debug3fmtCsZt7r1wRFCo_4test':
fake.c:(.text._RNvXsP_NtCs6aT7ng1d0qi_4core3fmtRjNtB5_5Debug3fmtCsZt7r1wRFCo_4test+0xa): undefined reference to `_RNvMs5_NtCs6aT7ng1d0qi_4core3fmtNtB5_9Formatter15debug_lower_hex'
/opt/arc_tools_202009rel/lib/gcc/arc-elf32/10.2.0/../../../../arc-elf32/bin/ld: fake.c:(.text._RNvXsP_NtCs6aT7ng1d0qi_4core3fmtRjNtB5_5Debug3fmtCsZt7r1wRFCo_4test+0xa): undefined reference to `_RNvMs5_NtCs6aT7ng1d0qi_4core3fmtNtB5_9Formatter15debug_lower_hex'
/opt/arc_tools_202009rel/lib/gcc/arc-elf32/10.2.0/../../../../arc-elf32/bin/ld: GOT and PLT relocations cannot be fixed with a non dynamic linker
/opt/arc_tools_202009rel/lib/gcc/arc-elf32/10.2.0/../../../../arc-elf32/bin/ld: final link failed: bad value
collect2: error: ld returned 1 exit status

demangled

src/lib.o: in function `<&usize as core[47ee6e850c258048]::fmt::Debug>::fmt':
fake.c:(.text.<&usize as core[47ee6e850c258048]::fmt::Debug>::fmt+0xa): undefined reference to `<core[47ee6e850c258048]::fmt::Formatter>::debug_lower_hex'
/opt/arc_tools/lib/gcc/arc-elf32/10.2.0/../../../../arc-elf32/bin/ld: fake.c:(.text.<&usize as core[47ee6e850c258048]::fmt::Debug>::fmt+0xa): undefined reference to `<core[47ee6e850c258048]::fmt::Formatter>::debug_lower_hex'

Is there anyway to use panic_semihosting with this crate?

Every example declares its own #[panic_handler] function.

When I use only panic_semihosting crate, I get an error stating:

  = note: arm-none-eabi-ld: /home/pi/.rustup/toolchains/nightly-armv7-unknown-linux-gnueabihf/lib/rustlib/thumbv7m-none-eabi/lib/libcore-c83b634e1f0ecbbe.rlib(core-c83b634e1f0ecbbe.core.2smtzb3g-cgu.0.rcgu.o): in function `core::panicking::panic_fmt':
          /rustc/043eca7f0b34d12e61c44206beca740628647080//library/core/src/panicking.rs:85: undefined reference to `rust_begin_unwind'

If I use both on the same time, I obviously get the duplicate error.

Right now, I have only been able to succeed with self-decleared panic-handler function.