Allowing heap allocating objects inside a short-lived scope to ensure freedom of memory fragmentation

Question

We're using C++ in an embedded system environment and basically don't want any kind of dynamic memory allocation (see for example Resources for memory management in embedded application for the kind of reasons why we don't). Still we don't want to do without some of nice C++-based features such as STL containers and std::string. For the first one we'd reserve a specific size at initialization and would not let the container grow beyond its capacity. For the latter (std::string) I was a bit skeptical on how to use them "safely" as they sometimes allocate memory on the heap.

I found circumstances, though, where it appears to be fine to use std::string (and generally other of heap allocating objects): I'd allocate the object itself on the stack (within a certain scope delimited by {} as I'm talking from C++) and allow them to allocate heap provided they actually free all their reserved memory when they get out of scope.

I understand that this method doesn't definitely guarantee freedom of memory fragmentation but I feel that if the scope at hand is short-lived this actually results in a contiguous free memory after the scope's end.

I also had doubts that there may be a problem when multiple tasks sharing the same heap but still the free memory shall be contiguous in the end provided the scopes at hand are all short-lived (do not block for example). Alternatively it would be acceptable to me that only one task is allowed to allocate memory on the heap and the others must not if that actually matters.

Is my suggested usage of heap-allocating objects valid? Does someone have another strategy to (partially) enable dynamic memory allocation without risking memory fragmentation?

Answer 1

We've done all sorts of C++ style dynamic memory allocation on tight embedded systems in the past. You just have to follow a few rules and be careful about mxing short and long term buffers. First, memory pools are your friend - as the article says.

Also, for all the small (<64 bytes) allocations that C++ loves to make in helping out with pairs, and control structures, a unit allocation scheme is essential - not only for fragmentation control, but also performance. A unit allocator preallocates a number of identically sized units of memory (say 64 bytes) and places them on a free stack. As memory is allocated, you pop them off the free stack and return them. Because all the sizes are identical, you only have internal fragmentation to the block size. Because you don't have to join memory when done, allocation and freeing is O(1) time.

Some other rules: If you need to make a dynamic allocation that will be long lived, don't have any short term allocations before it. Allocate the big buffer first, then the little ones so memory is not scattered. Another system would be to place long-term allocations on the back of the heap and short term ones on the front. We've had success with that as well.

You can also use multiple heaps (pools) to segregate different types of allocations. If you have something that is creating a whole bunch of short term allocations in one section of the code, while another section follows a different pattern, give them a different heap.

All the above, if followed carefully, will either prevent or limit fragmentation. Another solution is to use a relocatable memory allocation system where a low priority thread can re-order memory to keep it continuous over time. I've seen that done a few times as well - trading a little performance for 0 long-term fragmentation.

alloca can also help, but if you aren't following memory fragmentation prevention methods, you'll just end of scattering your stack as well - and as this tends to be a more valuable resource in embedded land, this may not be a good idea.

Answer 2

You might consider the not-so-popular alloca function to allocate variable-size variables on the stack. This way there is no fragmentation, but you may run into stack overflows if you use alloca for big variables.

Edit: some info about alloca from the GNU C library docs.