2
\$\begingroup\$

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
\$\endgroup\$
5
  • 3
    \$\begingroup\$ There's nothing unexpected about the behaviour of malloc and calloc. The challenge is that embedded systems often have very limited amounts of memory so care has to be taken to calculate your exact requirements. \$\endgroup\$ – Finbarr Apr 24 '19 at 8:36
  • 3
    \$\begingroup\$ Are you sure you have "no idea how much space you need"? Maybe you need to do some more analysis of the problem! \$\endgroup\$ – srl100 Apr 24 '19 at 8:51
  • 6
    \$\begingroup\$ If you have no idea how much space you need, how can you guarantee that it fits in the RAM of your microcontroller? This is a big part of the reason behind banning dynamic allocation. \$\endgroup\$ – pipe Apr 24 '19 at 9:47
  • 3
    \$\begingroup\$ @Finbarr Except running out of heap space, heap fragmentation, slow and non-deterministic allocation/freeing procedure... etc etc... \$\endgroup\$ – Lundin Apr 24 '19 at 10:45
  • \$\begingroup\$ Don't forget that any dynamic memory allocation system will use RAM to track its block allocation. This further reduces the amount of RAM available to your program. \$\endgroup\$ – kiwiron Apr 26 '19 at 21:27
8
\$\begingroup\$

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.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Dynamic allocation is always harmful and can't be used properly in embedded systems. Mostly because using it does not make the slightest sense. \$\endgroup\$ – Lundin Apr 24 '19 at 10:44
  • 2
    \$\begingroup\$ Nonsense. In some applications it can't make sense, in others it can be a sensible solution. Especially when you have a capable part that happens to be RAM-poor. I did a system that could be in multiple modes (determined at startup), it was very convenient to be able to malloc the structures for each mode. They wouldn't all have fit if statically allocated, and a generic solution for all modes would have been ugly. \$\endgroup\$ – Cursorkeys Apr 24 '19 at 10:57
  • 1
    \$\begingroup\$ There's something called the stack... Variadic allocation is one thing, unknown requirements is another. \$\endgroup\$ – Lundin Apr 24 '19 at 10:58
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ I disagree. Though I, too, strongly discourage dynamic memory allocation in systems without a capable MMU, the argument that dynamic memory allocation provides no benefit is not valid. With dynamic allocation you can kind-of time-multiplex the same memory location which can reduce worst-case RAM requirements: In theory, you can have two routines each using e.g. 60% of all RAM if those routines never try to use the RAM at the same time. \$\endgroup\$ – JimmyB Apr 24 '19 at 13:15
  • 2
    \$\begingroup\$ @JimmyB Reusing RAM between different routines is most often done by making memory-consuming variables local. When this is impossible, the next best thing is to implement your own memory sharing structure, e.g. a static union with a flag telling you which part is in use. Both these approaches are far more deterministic than malloc. \$\endgroup\$ – Dmitry Grigoryev Apr 24 '19 at 13:32
  • \$\begingroup\$ I agree. But this has nothing to do with having "an OS with dynamic tasks". And "[e]ither way, those 970 bytes will not be used" just does not hold. It can be used for other purposes, e.g. stack or more variables or..., so it does make a difference. \$\endgroup\$ – JimmyB Apr 24 '19 at 13:49
  • \$\begingroup\$ Heap cannot be used for stack, at least not easily. It can be used to hold more variables, but in the context of a single static task it's far better to allocate all memory from the start and use static unions or similar structures for shared storage. Sharing such structures among dynamic tasks is impossible, that's why you'll have to use malloc there. \$\endgroup\$ – Dmitry Grigoryev Apr 25 '19 at 7:45
  • \$\begingroup\$ "Heap cannot be used for stack" - Except on many embedded platforms which don't actually have strictly seperate memory regions (or memory protection) and where the stack will happily grow into the heap if either is larger than anticipated. \$\endgroup\$ – JimmyB Apr 25 '19 at 10:01
3
\$\begingroup\$

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

\$\endgroup\$
12
  • \$\begingroup\$ "You can't have an embedded system handling "an unknown number of inputs"" - Of course you can. Just don't try to keep all of the input in RAM at the same time. Receive/process data in pieces. I bet my AVR can "handle" the full 8GB of data from the attached SD card... \$\endgroup\$ – JimmyB Apr 24 '19 at 13:56
  • \$\begingroup\$ And no, the product specification won't always define the limits. Think about an embedded webserver. How can one specify the maximum amount of data someone will ever send in a single HTTP request to the webserver? \$\endgroup\$ – JimmyB Apr 24 '19 at 13:58
  • 1
    \$\begingroup\$ @JimmyB That's not an unknown number. It can have X kb of data in memory at the same time. That is the maximum limit, not the 8GB. It all boils down to your hardware having restrictions, always. You can't allocate infinite memory. In addition, when dynamic memory runs out in a PC everything will crash and explode very ungracefully. It's just that PCs have such vast amounts of memory including HD swap files, that programmers get away with writing crap. \$\endgroup\$ – Lundin Apr 24 '19 at 15:12
  • \$\begingroup\$ So by "number of inputs" you actually mean "the amount of data in RAM"? \$\endgroup\$ – JimmyB Apr 25 '19 at 10:13
  • \$\begingroup\$ "Product specification -> program specification -> MCU selection -> implementation." - That waterfall is a little too simplistic. Many times you can and have to trade implementation complexity or runtime for resource saving. So the implementation may yield HW requirements too. Take the webserver example again: If the spec says it should be able to handle data uploads of 10MB, would that imply that I need an MCU with at least 10MB of RAM? Probably not, but what amount of RAM will it actually require? \$\endgroup\$ – JimmyB Apr 25 '19 at 10:23
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ "You can keep allocating until some boundary is reached (like 80-90% of your memory)" You could as well have used 100% of the reserved heap section for statically allocated variables. Faster, safer, deterministic, less overhead. \$\endgroup\$ – Lundin Apr 24 '19 at 10:40
  • \$\begingroup\$ @Lundin ... True (I will update my answer). \$\endgroup\$ – Michel Keijzers Apr 24 '19 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.