Fast, predictable memory allocator for embedded stuff

[SiliconWizard]

So, I'm looking for a fast dynamic memory allocator for embedded software, with predictable run time and reasonable behavior regarding fragmentation.
Do you have anything to suggest, any experience you wanna share?

[Marco]

If it can't move stuff around the only reasonable thing to expect is a fast OOM error. I don't see how you could do a defragmenting allocator in C without some terribly hacky macro shenanigans, but someone probably made one in C++.

[Marco]

With a MMU you can use virtually over-allocated pools for fixed size blocks of geometrically increasing sizes and just throw the allocation in the smallest fitting pool. No fragmentation, just wasting some memory assuming randomly sized allocations.

[T3sl4co1l]

If it can't move stuff around the only reasonable thing to expect is a fast OOM error. I don't see how you could do a defragmenting allocator in C without some terribly hacky macro shenanigans, but someone probably made one in C++.

Not so impossible, but slower by design -- namely that double indirect pointers be used at a minimum.  That is, so that one big fat table of pointers, can be edited by the manager, as needed (at any sequence point, i.e. where the targets of those pointers aren't being held -- preferably only the outer pointers are passed between function calls, say), thus allowing the underlying memory to be physically sorted as needed.

Believe I heard the original Mac did something like this (as a strong preference, or a stipulation of the languages ran on the OS?), so it's not without precedence.  But yeah, slow having to double-tap all those pointers, especially on platforms with sucky pointer arithmetic (like, on AVR I can already see that taking another maybe dozen cycles per pointer access).

Also, what's wrong with malloc() (assuming this is a C project, and libc is available)?  Just an unknown?  Ah, but any allocator is an unknown until familiarized with; the real solution is just lots and lots of reading, heh.

And yeah, fragmentation depends entirely on usage pattern; perhaps a closer inspection of your application will lead to useful insights, as far as what you need and when; and then perhaps a less general solution will present itself, maybe something with arrays of structs/unions for a semi-static allocation (i.e. the objects are statically allocated but their contents varies by use).

Mind, I've not touched an allocator before, so, grain of salt, and for the most part I'm just curious to see actual answers, in preparation for when I actually finally need to write/use one.

Tim

[DavidAlfa]

I had to deal with the internal fragmentation in the T12 firmware.
For example:
-Allocate 200+200+400 bytes.
-Free the first 2x200bytes.
-Allocating 300 bytes didn't use the first 400 bytes, it was allocated after the 400byte block. Malloc saw 2x200b blocks, not 400b.

What I did to fix this was to allocate the 100% at boot time and then release it.
After that, all allocations were packed together when possible.
Also, this could be a poor implementation from ST.
I'm not a expert at this, there's probably a better explanation.

[DiTBho]

What I did to fix this was to allocate the 100% at boot time and then release it.

That's equivalent to static allocation, which is safe-by-design and it's the fastest solution ever.

Ram is cheap nowadays, I have recently seen this working model applied to the firmware of an industrial sewing machine, 512Mbyte of DRAM, everything is static allocated at compile time.

[David Hess]

I have seen memory allocators for real time systems which return results in bounded time.  Wouldn't Knuth's power-of-2 allocator meet this requirement?

[SiliconWizard]

I've looked at various allocation strategies. Was curious to see other people's take on this before exposing them.

Just a small "disclaimer" here first: not considering dynamic allocation for targets with very little memory available. To give an idea, I'd start considering this for memory sizes in the MBytes range.
While dynamic allocation is often frowned upon for "embedded" development (the term actually covering a pretty wide range of systems), there are cases for which static allocation *only* wouldn't really cut it, or would at least make your code harder to maintain and not very pretty.

Of course, general-purpose allocators here are to be avoided. The standard malloc(), for instance, is designed to work reasonably well for general-purpose use. Your requirements if you're writing a desktop application or embedded software with more constraints are absolutely not the same! Also keep in mind that using standard allocators such as malloc() is often actually several layers of allocators. You have the malloc allocator which in turn will ask for more memory from the underlying OS if needed, which is yet another allocator (or several!) On small embedded targets, this last part usually is very minimal - typically the sbrk() function implements a simple linear allocator.

So yes, using allocators adapted to your particular use is probably the way to go here. We may even have to consider using several different allocators at the same time for different use cases.

One of the simplest allocators is the "linear" allocator. It doesn't even need any header for each block. Allocate memory blocks linearly as they are claimed. Of course you can't free them individually, but you can free them all in O(1). That may, at first look, seem no different from pure static allocation, but it is different! In some use cases, allocating memory dynamically is more elegant, and you can still reclaim memory (although all at once) if needed, while reusing memory when allocated statically is a lot clunkier. It's also an interesting solution if not all allocations are known at compile-time - which can be the case when they can be known only at run-time.

You can reclaim memory partially using this scheme, using markers. AFAIR, Turbo Pascal had such an allocator, with the Mark and Release procedures. It's usable if your allocations are locally grouped and the groups have a similar lifetime. That actually covers a lot more cases than one may think. Region-based allocators are an extension of this.

Of course, this is a lot more problematic if you need a multi-threaded allocator, although you can always allocate dedicated per-thread regions. This would be less efficient in terms of memory use, though.

A power-of-two allocator is also an interesting option.

[rstofer]

Maybe the FreeRTOS Memory Management page can help:

https://www.freertos.org/a00111.html

There are 5 alternatives with increasing capability.  The source code is included with the distribution.

I would do everything possible to avoid having a heap.  I copy my string and conversion functions from "The C Programming Language" book (Kernighan and Ritchie) rather than use those from the C library.  I don't use printf() for the same reason.  I can usually get by with some form of puts() call.

I always look at the linker output and hope to not find _sbrk().  I won't provide one and I hope the environment doesn't provide one for me by default.  If the library doesn't include _sbrk() then it may be in syscalls.c provided by the IDE (eg STM32Cube)

I have no idea how you prove correctness when using dynamic allocation and an increasing call stack.

[SiliconWizard]

I would do everything possible to avoid having a heap.  I copy my string and conversion functions from "The C Programming Language" book (Kernighan and Ritchie) rather than use those from the C library.  I don't use printf() for the same reason.  I can usually get by with some form of puts() call.

I always look at the linker output and hope to not find _sbrk().  I won't provide one and I hope the environment doesn't provide one for me by default.  If the library doesn't include _sbrk() then it may be in syscalls.c provided by the IDE (eg STM32Cube)

Unless I missed your point, looks like you are directly associating dynamic memory allocation with the standard "heap" and the standard allocator.
I think I was clear in that I wouldn't consider using that. So, it would be a fully custom allocator (or set of allocators) having nothing to do with anything standard.
(That said, you're right saying that some C std functions do themselves call malloc() and thus should be avoided in that case.)

I have no idea how you prove correctness when using dynamic allocation and an increasing call stack.

You may want to elaborate on this a bit. Otherwise, as it is, all I understand is that you're concerned with how the stack and heap could grow into each other, something I think we already discussed when talking about stacks.

Avoiding the "heap" to grow into the stack, even using the std malloc(), is easy. You just need to write _sbrk() appropriately so allocation can't go further than a predefined end of the heap. That means you need to "reserve" space for the stack, even if you don't use it all. That's the only way of making things safe IMHO.

Avoiding the stack to overflow into the heap, OTOH, is a more severe problem, which we also talked about in threads about stacks. Various ways to ensure that, some requiring a MMU if you have one, some requiring more "manual" checking inside your code, which always has some added cost.

But even so, that's still thinking about it in very very standard terms, which I was not here. In the very basic standard memory layout, especially on small targets, there's only one "heap" - all memory between the end of the statically allocated memory and the end of the stack, and then the stack, growing downwards.

Of course, a completely different memory layout could be used here.

[Jeroen3]

What do you need it for? Can you get away with writing a container class that performs as an adapter between the memory and application code?
For example, the qstring classes? When you do operations with them they internally work as linked list. (read, lots of small allocated blocks)

[SiliconWizard]

I forgot to mention pool allocators, of course, which can be put in the set of efficient allocators to be used in specific cases. They allocate blocks all of the same size, which makes it very easy and fast to handle.

Regarding the relative aversion to dynamic allocation, common in embedded development, we need to consider when it is reasonable and when it is just "magical thinking". The latter is true in many cases.

Like with any tools, we need to use the ones adapted to the application and use them with due care.
A common issue with dynamic allocation is that, due to its dynamic nature, many developers will tend to use it carelessly, because it makes things easier, rather than carefully. A bit like with dynamic typing.

Using the right allocators and the right techniques, I think you can absolutely make it safe and provable - using, for instance, pre-conditions, invariants and post-conditions, as with any other part of software.

[SiliconWizard]

becasue even philosophically, it has its meaning: "eternalism" vs "presentism"

As you probably figured, you're going a bit far here.

That said, there are underlying questions that can be interesting, as to what we define as dynamic and static from the POV of a program's execution.
Any "useful" program is dynamic in nature. It will take different paths of execution, will set variables and fill memory with different values, will modify the stack in different ways, etc.

Should memory allocation be considered fundamentally differently?
One thing first: using stacks is a form of dynamic allocation. As soon as you have a stack, you can't claim you're not using dynamic allocation at all..
But it's a form of "automatic" allocation. So it feels a bit safer. That should tell us something: it's a lot about the lifetime of allocated objects! Which is why allocators for bounded lifetime objects are often considered as an alternative to general-purpose allocators when performance and safety matters.

Which gets me to the point: the kind of allocators I'm thinking of here are those that deal with bounded lifetime objects, not only making the allocators simpler and faster, but also avoiding a whole range of issues related to objects lingering in memory with an ill-defined lifetime and the associated risks of leaks, or using an object that has beed freed...

Just some thoughts.

[T3sl4co1l]

Kind of an interesting question to turn on its head: if your habit is to divide things into "eternal" vs. "present", why is that?  What about things that are intermediate?

Similarly, turn around the question: what's actually dangerous about memory allocation?

The answer may be much more related than you might otherwise think...

It sounds to me like the biggest problem with memory allocation is, no one teaches how to think about, or use or write, allocators, so people just think of them as magic.  (At least, that would seem a possible explanation.  I don't recall taking an undergrad course that discussed the topic; heck, the most relevant course I took used Java. So, uh, yeah?)  "Just go malloc() some memory, it always works. Except when it doesn't, but nevermind that, the calls have always returned successful for me!"  We grant ourselves these carve-outs of responsibility, a willful ignorance of things that are, at least not necessarily, any more complex than anything else we're working with.  And yet we have the audacity to complain when these things do finally go wrong.  Instead we must question such assumptions, and see if there might in fact be some underlying truth we missed: perhaps making a binary distinction was hasty, perhaps the real thing is multidimensional, or continuous, and we've sliced it the wrong way; etc.

But also, not that this is actually answering the question, so I digress.

Tim

[DiTBho]

Kind of an interesting question to turn on its head: if your habit is to divide things into "eternal" vs. "present", why is that?

Only because I usually prefer to study things that I can describe in phase space, a space in which all possible states of a system are known and represented, and each possible state corresponds to one unique point in the phase space.

If you want a "predictable" memory allocator, the space space offers the best way to mathematically study and describe it.

[DiTBho]

what's actually dangerous about memory allocation?

you need to allocate a buffer for a task that must be completed in a deadline, and there is no free memory.

If we talk about the industrial sewing machine above, its control unit has to complete the texture-motion planning within a deadline, this requires to allocate a couple of buffers with critical things to do, if malloc returns NULL because al the memory is busy, you can't wait for a chunk of memory to be released as free (you can wait on a Linux desktop), so you can't allocate the buffer in time.

The result is catastrophic: 200 hundred sewing needles draw a funeral line on the curtain, making it garbage.

[Marco]

Not so impossible, but slower by design -- namely that double indirect pointers be used at a minimum.

The issue is the syntactic sugar. With C++ you can add that as a variation of smart pointers, with C it will require a lot of macro hacking and the code becomes even more error prone than standard C.

[DiTBho]

With C++ you can add that as a variation of smart pointers

any C++code-example of that? 

[Marco]

any C++code-example of that? 

Can't easily find any, guess I was wrong. Did find a paper on implementing a defragmenting allocator in C though ... they don't use macro's and will thus require even more finnicky and error prone application code.

http://www.fp7-save.eu/papers/SIES2016.pdf

PS. no actual code, but it seems game/console programmers use defragmenting allocators in C++ with smart pointers.

[SiliconWizard]

what's actually dangerous about memory allocation?

you need to allocate a buffer for a task that must be completed in a deadline, and there is no free memory.

And as I, and T3sl4co1l said, this is all a matter of software design, and not an intrinsic problem.
What you mention becomes a problem if you use memory allocation as a magic tool.
What I agree with is static allocation only is much safer in the hands of people not mastering memory allocation patterns, and I admit this isn't a simple topic.

[SiliconWizard]

That said, the kind of allocators I mentioned are commonly used in embedded settings, or just when speed and predictablity matters.

The Linux kernel actually implements slab (in the form of power-of-two IIRC) and pool allocators, for instance.

So I' m just going to start with that: implementing linear (also called "bump"), slab and pool allocators. And think of how to best use them and of appropriate allocation patterns. Certainly, it requires a different approach than just using malloc() frantically every time you just need some memory without giving it another thought.

https://en.wikipedia.org/wiki/Memory_management
https://en.wikipedia.org/wiki/Region-based_memory_management
https://en.wikipedia.org/wiki/Slab_allocation

[DiTBho]

This is all a matter of software design, and not an intrinsic problem.

static allocation is safe by design, dynamic allocation always exposes a probability of disaster due to the  Murphy's law, it can be demonstrated mathematically.

[SiliconWizard]

Believe I heard the original Mac did something like this (as a strong preference, or a stipulation of the languages ran on the OS?), so it's not without precedence.

It absolutely did that. I programmed for Mac OS at the time. The allocator would return "handles" to memory blocks. You'd get the actual pointer to the block - strictly when needing to access it - using some kind of Lock() function. It would lock the block and return a pointer to it. Then you would unlock it as soon as possible. Once unlocked, the OS could move the block around to defragment memory.

Remember that the first Mac had only 128 KB of RAM, so that was necessary.

I think a similar approach existed on Windows as well. IIRC, the API provided at least one allocator that would behave like this.

And "kids" these days think that manual memory management with malloc() or the like is hard...

Of course that "solves" fragmentation issues, but doesn't solve the predictability problem, on the contrary.

[SiliconWizard]

This is all a matter of software design, and not an intrinsic problem.

static allocation is safe by design, dynamic allocation always exposes a probability of disaster due to the  Murphy's law, it can be demonstrated mathematically.

And, again, as T3sl4co1l and I said...

- You can also prove mathematically that a given function returning a constant is much safer than a function returning a value based on a set of inputs and a complex calculation.
- You can also prove that the probability of bugs is much lower if your whole program has only one execution path rather than several (but that program would probably not be that useful...)
- Again using a stack is dynamic allocation. Interestingly enough, many people seem to either ignore it, or just think that it can be risky only if using recursion.

So, this is interesting.

Even more interesting is to, OTOH, find use cases for which dynamic allocation (done properly with the right allocators) could actually be safer than just relying on static allocation. Or even if not safer, could at least be the only reasonable way of implementing things.

So, that's some food for thoughts. That said, my thread is not about finding reasons why dynamic allocations should not be used. Otherwise I wouldn't have started it. If I'm considering it, there is probably a reason. If I was interested in reading all the reasons why it should be avoided, the material about this is not missing...

Oh, and I think the example I gave with the Linux kernel is sort of interesting.
Try and rewrite it with static allocation only, and see how far you go and how scalable it will be.

[Siwastaja]

- Again using a stack is dynamic allocation. Interestingly enough, many people seem to either ignore it, or just think that it can be risky only if using recursion.

This is a fair point. I see it like experienced programmers coming up with a hand-wavy (but indeed, unscientific) way of leaving a lot of margin, like reserve 32KB for stack and only use a few dozen bytes per function and no recursion or very deep call chains, and anything beyond a, say, 16-byte buffer, go for static storage instead.

This can be made quite robust with static analysis tools that can understand worst case code paths. Or, just trusting the experience of the programmers combined with a lot of margin.

I don't think I have had stack overflow in... 15 years? The strategy for using stack only for a few local variables, no larger buffers at all, is simply clearly working.

Am I wasting more RAM statically allocating buffers? Maybe, that's the obvious downside of static allocations.

Using unions in the "original" fashion is a pretty interesting way of saving memory in the obvious cases where static allocations are different in different parts of software between which buffer retention is not needed. The almost grotesque explicit nature is the safety net here; you need to document it so explicitly that making a mistake is somewhat unlikely.