Memory allocation in embedded software development

Question

In embedded systems, the use of dynamic allocation is strongly discouraged. MISRA C do not allow using malloc and calloc because of their unexpected behaviour. My question is: How do you handle memory allocation when you have no idea how much space you need ? How do you initialise an array before using it ? In the example below, is it really better to allocate 1000 values and end up using 30 values because you don't know how many values you really need ?

#define MY_ARRAY_MAX_SIZE 1000
/**
* 
* some code ...
*/

// Init
uint8_t myArray[MY_ARRAY_MAX_SIZE];                              // Approach 1

uint8_t myArray[MY_ARRAY_MAX_SIZE] = {0}                         // Approach 2
/* OR */
memset((void *)myArray, (uint8_t)0, MY_ARRAY_MAX_SIZE * sizeof(uint8_t)); // Approach 3

Answer 1

In the example below, is it really better to allocate 1000 values and end up using 30 values because you don't know how many values you really need ?

In my experience, this is not a problem I've actually faced. Requirements tend not to be that dynamic.

If you have, say, 12 8-bit ADC channels you need to datalog every minute for a rolling 1 day period then you know that you need a buffer of 1440 * 12 uint8_t elements and can statically allocate that.

The closest you generally come to your hypothetical is things like UART rx buffers. The solution here is to allocate a larger buffer that you determine you will need. This isn't a problem useless you are short of RAM, and the amount of slack doesn't usually need to be large.

And, as others have said, dynamic allocation isn't considered harmful in embedded systems if it is done properly. I do tend to avoid it though because it significantly increases design complexity and testing requirements.

Answer 2

You statically allocate memory for the worst case that you intend to support. If you intend to support up to 1000 values, create an array of 1000 items. Plan what you want the software to do if you ever exceed that limit.

If you don't know what the worst case is, go back and work it out. Embedded systems don't normally have virtual memory with swapping/paging to disk when they run out of physical memory. You can't just keep malloc'ing more memory forever.

If the system runs out of memory on start-up, then there is a mismatch between what you are trying to do and the capability of the computer you are using. At least you know that on start-up, rather than when malloc fails some way down the line, when you're least expecting it.

Answer 3

How do you handle memory allocation when you have no idea how much space you need ?

You specify as much as you need to handle the worst case scenario. Not more, not less. You can't have an embedded system handling "an unknown number of inputs".

The maximum amount of memory needed is directly inherited from your product specification. It is a deterministic amount and it can be decided at compile time. Does your product need to handle 1000 array items? Then pick array size 1000 and pick a MCU with sufficient memory.

See https://electronics.stackexchange.com/a/171581/6102

Do this:

Product specification -> program specification -> MCU selection -> implementation.

Don't do this:

MCU selection -> implementation -> no more memory -> program specification -> MCU selection 2

Answer 4

Dynamic memory allocation only makes sense if you have an OS with dynamic tasks.

On an embedded system your software is the only thing that will ever run. So you have an option to allocate 1000 bytes (and use only 30) or allocate 30 bytes and keep the rest lying in the heap. Either way, those 970 bytes will not be used, so there is no reason to bother with dynamic memory.

Answer 5

The problem with dynamic memory allocation is just that it quickly becomes non-deterministic. First, in contrast to static allocation, dynamic memory allocation is not checked at compile/link time, so you generally will have to manually estimate/analyze how much memory in total will be dynamically allocated at runtime. Then, at runtime, allocations/de-allocations may be unpredictably slow and, much worse, they can easily cause fragmentation of free memory which is often an unrecoverable condition once it has progressed somewhat. Memory fragmentation is really bad because it will cause out-of-memory errors although, in total, there's enough free memory, and that's why it's almost impossible to predict. (It depends on the algorithm(s) the memory allocator implements and the size and sequence of allocations and de-allocations. Especially the latter may be impossible to predict if the system uses different allocations/de-allocations in response to external stimuli.)

is it really better to allocate 1000 values and end up using 30 values

Often it's not better.

It is a common error and cause of many bugs and/or vulnerabilities when people just assume an upper bound on some data which just is not specified.

Example: Say my device provides some kind of serial terminal functionality, i.e. some kind of user can send certain commands. A common, simple approach is to read characters into a buffer until e.g. a CR or LF is encountered. The developer may go about and check that the longest valid command is 30 characters long and use that to set the size of his buffer to, say, 30*2 characters, to provide "enough" of safety margin in case he overlooked some possible lengthy command arguments.

However, setting a fixed limit on a buffer and assuming that it will not overflow "because" is just not safe.

The point here is that the majority of buffers and the like are either of a small, fixed (worst-case) size because they will only hold a specific data structure, or are not bounded at all because data comes in from some untrusted/uncontrolled source.

Thus, coding purely based on an estimation of a 'reasonable' worst-case is not enough.

The only (safe) way to handle arbitrarily large data with non-infinite RAM is to process data in parts. Receive a buffer's worth of data, process as much of it as is possible, then receive more data until done. Of course, parsing a full command line from a single contiguous block of memory is much easier than parsing and piecing together multiple parts, storing intermediate states in between, but "easy" is just not the same as "robust" in most cases.

TL;DR

Don't (statically) allocate "probably enough" memory. Prepare for your buffer to be definitely too small at some point and process that case gracefully. At the very least, detect and reject input that would overflow the buffer. If you can, try and handle arbitrary input sizes constructively.

Answer 6

First, the problem is not the allocation, but freeing the allocated memory. This (can) lead(s) to memory gaps and pointers pointing to 'nothing' (so called dangling pointers).

So one 'solution' is to not use any freeing function but only (dynamic) allocation. You can keep allocating until 100% of the heap space is used (see remark Lundin below).

Another option is to create a big buffer and store your data 'manually'. E.g. if you have many dynamic strings or objects from the same type (preferably) to store them in a preallocated array and store pointers within that array. If you have two 'sets' of objects to store, either if one has length 20 and the other 800, or the first has 800 and the latter 20, both will fit. However, also here, freeing is hard (unless you write your own freeing functions but this leads to the same problem as above).

Update

I'm currently trying a project where I need a lot of memory, but not all at the same time. So I'm planning is:

• Copy some data from an SD card into SRAM memory. (if you use this method, calculate if the SD read times are ok, or if you need to write, the SD write time).
• If I need more memory, I will add external SRAM memory (like 32K256 or 23LC1024). However, one cannot directly 'create' variables here, so one has to use a pointer and move back/forth data from it to your MCU's internal SRAM.