Heap allocation considerations for embedded systems

[PTaylor-us]

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]

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]

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]

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]

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

[adamgreig]

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]

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

[timblakely]

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

[MaderNoob]

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.