Malloc and it's use in MCUs

[ilbs]

Hello everyone,

I have a project which needs to work in real time and can't
afford to hang or undergo  any access violation issues during
its execution. I typically use malloc/free  extensively!!! Then, I
stumbled on the first few paragraphs of the following article:

(see around the middle of the article under
"Memory Fragmentation")

http://www.design-reuse.com/articles/25090/dynamic-memory-allocation-fragmentation-c.html

Now I am worried! If using malloc in MCUs such as pic32 can cause
memory fragmentation, which may cause our programs to hang, then
why should we ever use malloc for embedded systems...
more over, why do compilers for MCUs even offer the possibility
of memory allocation if using malloc can represent such a risk?

Kowing this, really discourages me as it leads me to wonder why did I
bother learning how to malloc arrays, structures, arrays of structures
and arrays of pointers for??

My question is, should we or not use malloc in MCUs ?

Also, if one allocates say 50k in ram, would it be safe
to malloc 3 or four mallocs of 5k each? I don't see how
any problems can arise with this sort of leeway!

thanks

[andyturk]

Avoid malloc() if you can in systems with limited memory.

If you can't avoid it, you'll be better off if all the allocations are the same size. That'll prevent fragmentation in the heap. The next step up is to look at buddy system allocators.

Oh, and that article is incorrect about C++ requiring dynamic memory allocation--there's nothing in C++ that requires you to call new or malloc.

[mikeselectricstuff]

If possible, don't use dynamic memory at all.
If you need to, if possible allocate it it once and never free it.
If you don't know in advance how much memory you need, how do you know you will always have enough?
Otherwise make absolutely sure you understand how the particular malloc/free implementation in your compiler works, and make sure you can deal with any problems it may cause gracefully ( or recognise that at some point you may just need to do a reset to recover).
One scenario is where you need different size/shape buffers, but at different times and never at the same time - this can be better handled by a large static allocation of a union which provides the necessary buffer types within the same memory.

Every application has different requirements so there is no "right" or "good" answer. You just need to understand what's going on at the low level, and figure out an acceptable way of dealing with it.

non-essential use of Malloc/free is a classic error by poeple coming from a PC type environment who don't understand the limitations of small MCU systems.

[Rufus]

Now I am worried! If using malloc in MCUs such as pic32 can cause
memory fragmentation, which may cause our programs to hang, then
why should we ever use malloc for embedded systems...

Microchip won't supply the source code for their run time libraries so you have no idea how it will perform and is reason enough to not use their heap management functions in reliable embedded systems. They grudgingly provided some source code to dump information from their undocumented heap control structures for C30 which carried over to XC16. I can't see the same in the XC32 distribution.

Some (anally retentive) will state that dynamic memory allocation should never be used in embedded systems. Reality is much less black and white. Dynamic management does not cause programs to hang. Allocation and freeing may take varying times and violate real-time requirements. Allocation may fail when heap becomes fragmented which may or may not be a difficult thing to manage.

The likelihood of trouble depends on allocation sizes, patterns, lifetime, and how the heap is managed.

[Bored@Work]

Some (anally retentive)

It is not anally retentive when you avoid a risk. Unfortunately there is now a generation of "programmers" who give a fuck about robustness and safety.

[Rufus]

Some (anally retentive)

It is not anally retentive when you avoid a risk. Unfortunately there is now a generation of "programmers" who give a fuck about robustness and safety.

It is anally retentive to avoid a risk which doesn't exist. See it all the time. Someone did X and screwed up badly therefore no one shall ever do X again regardless of X being the best solution and not screwing up in 90% of cases.

[Mechatrommer]

Now I am worried! If using malloc in MCUs such as pic32 can cause
memory fragmentation, which may cause our programs to hang, then
why should we ever use malloc for embedded systems...

because its easy. thats what higher level language is all about. other aspect is uniformity or portability between mcu's. they are many "resourcefull" mcu out there and are the right spot for malloc.

more over, why do compilers for MCUs even offer the possibility
of memory allocation if using malloc can represent such a risk?

because the compiler's designer "brilliantly" knew that there are some people out there that will handle malloc (they opted to use instead of not use) with cautious and wisdom on limited resourced mcu.

Kowing this, really discourages me as it leads me to wonder why did I
bother learning how to malloc arrays, structures, arrays of structures
and arrays of pointers for??

assuming the compiler is perfect and bugless! if not, you should worry why you want to use higher level language at all in the first place? learn assembly and get acquainted! then you should know the cutting line by then for a particular system. and if you have experienced things like semantic errors, you'll know the "tools" or "existing bugs" is the least of your problem. the problem is how to use them wisely or not use them at all. the link you provided is one step to become a wiser programmer and i'm not saying i'm wiser enough. did i wander off? sorry. maybe too much time on my hand

non-essential use of Malloc/free is a classic error by poeple coming from a PC type environment who don't understand the limitations of small MCU systems.

more accurately begineers, or who are too young to know "limited resource PC type environment" many years back, or who give a fuck on safety and how things work.

ISTR that there is a variant of malloc that will return NULL if it cannot find one continuous block of memory or maybe it depends on the OS used. but i can be mistaken my memory is rusted already.

[marshallh]

Use structs of structs. Encapsulate your entire memory usage within 1 struct at the end.
It's entirely possible and I've done it, it works great when you have a constrained use case and can use the stack for most things instead of malloc.

[IanB]

An embedded program should ideally be fixed in scope and predetermined in its functions (for example, the console display in a car). As such, it should be possible to predict ahead of time what memory is required for what purposes and to pre-allocate by design for each task.

General purpose memory allocators like malloc and free are designed to support general purpose programs on general purpose computers where the resource requirements are variable and not known in advance. A user of a general purpose program has huge freedom to impose different demands on the program at run time in a way that should not happen with embedded firmware.

So if you find yourself wanting to use malloc for memory management, ask yourself, why can't I predict this need when I'm writing the program, and why can't I design in a suitable buffer size at compile time? (If memory is limited you may need to use overlays of different structures in the same space to handle different tasks of course.)

[Rufus]

Use structs of structs. Encapsulate your entire memory usage within 1 struct at the end.
It's entirely possible and I've done it, it works great when you have a constrained use case and can use the stack for most things instead of malloc.

Seems entirely pointless. The reason for using dynamic memory allocation is to allow the same memory to be used for different things at different times.

[marshallh]

You're right. But it all depends on the application. Your app may never have to switch contexts away from the working set of data. Or maybe it has 3 major operating modes, in which case you could switch overlays at runtime.

[nctnico]

Use structs of structs. Encapsulate your entire memory usage within 1 struct at the end.
It's entirely possible and I've done it, it works great when you have a constrained use case and can use the stack for most things instead of malloc.

Seems entirely pointless. The reason for using dynamic memory allocation is to allow the same memory to be used for different things at different times.

That is precisely what the stack does. In some cases you just don't know how much memory is needed at compile time. You have to do a worst case analysis in such cases but allocating at start and never freeing the memory is a perfectly workable solution. BTW even on embedded Linux systems with no swap and several hundred MB of memory fragmentation can be a problem.

If you need dynamic buffers in a microcontroller an good technique is to use a linked list with pieces (blocks) of memory. A chain of blocks represents a buffer. Actually you can extend this system to defragment the chains in case you need to allocate a contiguous block to emulate malloc. Either way the application must have a fall-back scheme in case the system is temporarily out of memory and the application must be designed so all blocks are freed when no longer in use.

[andersm]

Microchip won't supply the source code for their run time libraries so you have no idea how it will perform and is reason enough to not use their heap management functions in reliable embedded systems. They grudgingly provided some source code to dump information from their undocumented heap control structures for C30 which carried over to XC16. I can't see the same in the XC32 distribution.

The same function is present in the XC32 libraries.

[Rufus]

They grudgingly provided some source code to dump information from their undocumented heap control structures for C30 which carried over to XC16. I can't see the same in the XC32 distribution.

The same function is present in the XC32 libraries.

Well if it is the same function as in XC16 fprintfing to stderr it is not exactly convenient efficient or useful. The source is distributed with XC16 so it can be used as an example for creating your own runtime checks and monitoring. I didn't find source in the XC32 distribution.

[westfw]

why do compilers for MCUs even offer the possibility of memory allocation if using malloc can represent such a risk?

Because sometimes (frequently!), the benefits outweigh the risks.  And frequently the risk can be analyzed into near non-existence.  And there are risks to complicated schemes of non-dynamic memory allocation as well.

(that said, I am frequently horrified at the poor "instrumention" of most memory allocation code.  The malloc() I used most included a "show memory" command that would show every block of dynamic memory, who had allocated it (or last freed it), and much other data.  Most MCUs you can't even find out how much memory is available.)  (Of course, there's overhead to this.  Leading to "malloc_lite()" for those instances where you didn't want to put up with that much overhead.  and "chunks" for when there were a bunch of fixed-size things that you needed to allocate from ISRs.  And periodic rewrites over the span of of the 4000x change in "typical" memory configurations over 20 years when various misbehaviors were discovered.  And bugs in the code that used all of the above, of course.)

[IanB]

It is also not obligatory to use the default memory allocator provided with the system, which is written in a general purpose way to suit all foreseeable requirements. If you have more specific requirements you can write your own allocator that can be optimized for your needs.

[ilbs]

Yes, but guys, what if we are careful not to malloc more than
4 blocks at a time? For example, leaving lots of leeway,
4 blocks of 25 bytes each with a heap size of 10K!!!

I don't see how this scenario can cause fragmentation???

even if the 4 blocks were 1K each but never surpassing 4 blocks
at any given time is still very possible because there will always
be enough room to free 1 to 3 blocks and then subsequently
malloc 1 to 3 blocks !!!

I don't see a problem with this... in any case I have tried stuff
like this and the MCU ran for days without any problems
but I never went more than 4 blocks at a time while
always respecting the proportion between heap size to block size
for example (heap size/block size=10K/1k).... which means
ideally the heap can support 10- 1K blocks where as I am only
using 4-1K blocks!!!!

Unless I am missing something.... I think malloc can be used this
way and be very safe. I thinks it's when we malloc huge blocks of memory
per heap size that creates problems.... for example:

Heap size: 10K
Block size: 3K to 5K
# of Blocks used at the same time: 3

... then I believe we would have issues!!!!

PS. I would use it as for each block can *vary* from 1 byte to 10K bytes.


thanks for replies!
 

[Mechatrommer]

I don't see how this scenario can cause fragmentation???

you are at the mercy of the library internal implementation, there can be additional storage needed internally for housekeeping. if you can look at the library's code then do so, if not then.. code once debug twice.

I don't see a problem with this... in any case I have tried stuff
like this and the MCU ran for days without any problems

running MCU for days is not a good idea to ensure the safety of the code. "simulate" every possible inputs and operations, abuse it and make worst case scenario is the right thing to do. sure there will be compromise for this depending on the severity if the program fails.

[zapta]

OP, you are very right to worry, I also would worry. The fact that malloc exists does not mean that it is good for your application.

Your best bet is to allocate your resources in advance (you can static structs with arrays, etc, more memory efficient than malloc BTW). If you need to dynamically allocate items (e.g. new items for lists), implement your own 'allocation' over the item pools you created during initialization, e.g. have a list of free items and move between lists. If your data is of variable type/size, you can have multiple pools or make them unions as Mike suggested.

Beware also of library functions/classes that may use malloc/new post program initialization, they are just as risky.

The C heap cannot compact itself so it is non deterministic in general (unless if you prove somehow that your specific allocation/release pattern will never fail).

[free_electron]

MALLOC is an instruction that should ONLY be used on systems that dynamically load a runtime.

A microcontroller system does not fall in this category. A microcontroller system runs from a rom. This predicates that the memory layout is KNOWN at compile time.

[nctnico]

Like I typed before: the memory layout is not always known at compile time. It can depend on the system's configuration. Malloc once and never free is a perfectly valid technique.

A much better way would be to use a C++ compiler. C++ allows to allocate arrays which are sized at runtime and cleanup up automatically when they go out of scope. Still you'd need to do a carefull examination of the worst case memory requirements.

[andyturk]

Malloc once and never free is a perfectly valid technique.

Yup.

C++ allows to allocate arrays which are sized at runtime and cleanup up automatically when they go out of scope. Still you'd need to do a carefull examination of the worst case memory requirements.

In a single-threaded system, your heap and stack will share a boundary so it's not such a big deal. But if you're using multiple threads, you'll need to know how much space you need for each stack and that gets complicated quickly.

[ejeffrey]

Another option for many c implementation is alloca.  It allocates a dynamic length buffer on the stack, and automatically frees it when it goes out of scope.  You still have to be careful: you can easily run out of stack, but you won't have memory leaks, and you can have some wiggle room in knowing how big your structures need to be at compile time.

Also, be warned that avoiding dynamic memory management can also destroy your program.  If you have heard of 'buffer overflows', they used to be responsible for the majority of security breaches on the internet.  In most cases, those were due to people using fixed length buffers because it was easier than dynamic allocation, then one day a bit of data came along that was bigger than they could handle.  Crash, and possible security breach ensues.  Dynamic languages and use of high level libraries to handle dynamic memory management in languages like C and C++ have mostly eliminated these problems in the PC world and made way for new and more complicated security breaches, but lots of embedded software is still designed that way.

So basically, you are damned if you do, damned if you don't.  Software development is hard.  Programs are complex, and anticipating every possible circumstance and every possible state is generally impossible.  You have to do the best you can to anticipate everything, then code defensively around the assumption that you didn't.

[westfw]

Use of a data stack should be avoided in any microcontroller architecture that is incapable of detecting stack overflows and underflows of that stack.  Preferably, avoid stacks unless you can allocate substantial areas of inaccessible memory other either side of the stack, so that buffer overflows of local variables can be trapped.  In addition to buffer overflows, inadequately tracked call depth can cause data stack areas to collide with static data.  All data should be pre-defined; allowing "local" data to be allocated on a stack is no better than allowing malloc().   If your processor lacks a dedicated hardware stack for use as a subroutine call mechanism, it should use some other mechanism for subroutine calls.  Some HLLs have "goto" and "computed goto" statements that can be used (with some care) for subroutine calls; avoid HLLs that insist on using a stack for such purposes.

Note that modern CPU architectures (ARM, MIPS) DO support subroutine linkage schemes other than stacks.  If we're going to have reliable embedded firmware, we have to mate the architectures with better HLLs!

 :-)

[nctnico]

You can check the stack with every microcontroller. If you sample the stack pointer in a timer interrupt you can see if it has advanced too far and take action. Its a bit like a random time sampler but after a while it will get a worst case value.