Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Heap allocation considerations for embedded systems #36

Open
PTaylor-us opened this issue Jun 5, 2020 · 8 comments
Open

Heap allocation considerations for embedded systems #36

PTaylor-us opened this issue Jun 5, 2020 · 8 comments

Comments

@PTaylor-us
Copy link

PTaylor-us commented Jun 5, 2020

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.



@PTaylor-us
Copy link
Author

My plan is to eventually create a PR using the https://github.com/japaric/tlsf repo unless someone convinces me that's not a good option before then. I'd love to get some feedback and thoughts. I certainly don't want to invest a lot of time in it if I've overlooked something important.

@therealprof therealprof added the nominated Issue nominated as discussion topic for the Embedded WG meeting label Jul 20, 2020
@therealprof
Copy link

therealprof commented Jul 28, 2020

As discussed in todays meeting:

@japaric currently not working on tlsf but happy to transfer ownership
rust-lang/libs team is making progress on making collection allocator agnostic
rust-lang/lang team is slowly making progress on stabilising the global allocator

Thoughts from @japaric:

  1. do we want to change the underlying allocator of alloc-cortex-m?
  2. we could create a thin global-tlsf-cortex-m something crate that turns tlsf into a global_allocator

Probably need to explore options a bit.

@PTaylor-us
Copy link
Author

If there is currently no plan of whom to transfer ownership to, I'd be happy to take it.

I do believe that the underlying allocator of alloc-cortex-m should be changed to something besides the current or allow selection of the allocator in some way.

My thoughts (perhaps a bit naive), are that the core or tlsf should be hardware agnostic and perhaps use feature flags to select the hardware platform (eg. cortex-m) or have multiple platform-specific crates that depend on the tlsf crate. I know there was a comment along the lines of not wanting to clutter the crates.io namespace with a bunch of tiny adapter crates. I agree with that concern.

@therealprof
Copy link

Discussion from todays meeting: No updates, will check in again next week.

@adamgreig
Copy link
Member

Hi @PTaylor-us, we were discussing this issue again in today's meeting. Are you still interested in working on this? The general consensus was that this still seems like something that should change, and TLSF seems a good candidate; we'd presumably need to get TLSF published first?

@PTaylor-us
Copy link
Author

@adamgreig It is something I'm still interested in. However, I don't know when I'll have time to work on it.

@adamgreig adamgreig removed the nominated Issue nominated as discussion topic for the Embedded WG meeting label Apr 6, 2021
@timblakely
Copy link

Looks like there's another more-recently-updated implementation of TLSF published on crates.io: RLSF https://github.com/yvt/rlsf

@MaderNoob
Copy link

The provided tlsf allocator does not utilize memory properly, especially in cases with large alignments, where even allocation of 4 bytes can create a chunk of size 1024 or even 2048 if requested to have an alignment of 1024 for example.

I created an alternative memory allocator which solves this problem and provides much better memory utilization. With my allocator, an allocation of 4 bytes will only use 4 bytes, plus a usize for the header. The same is true for every size and alignment requirements that are provided to the allocator.

About linked list allocator, it has a serious bug where it leaks memory and loses it forever, which over time will lead to heap exhaustion even in cases of low memory usage. My allocator also provides much better performance then linked_list_allocator, as can be seen in the readme.

I would strongly advise you to use my allocator, since it provides much better memory utilization, which is essential for memory constrained systems, and it provides very good performance.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants