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?

Magdau

It's hard to answer without knowing the system you're using. I for one work on embedded Linux and never had memory fragmentation problems even though the memory is small (64MB) and the device stays on all the time. – Dialectologist

@syam: 64MB==small? I'd regard 64*K*B as large in some of my projects :) – Devitalize

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.

Bird

Is this what is sometimes referred to as a "Pool allocator" ? I was wondering if it could help for this kind of issue. – Robustious

I've forgotten to precise that we actually prefer to use memory pools for long-lived objects. I was definitely asking for short-lived objects. I thank you for the answer as it gives me a lot of food for thought but still I miss a confirmation that my scope-based approach is valid. – Magdau

Scope based memory works as long as you don't mix a long-term allocation on the same heap/pool as your "scoped" allocation. That is the best confirmation I can give you. – Bird

I don't think people are understanding alloca with C++. The memory won't scatter, it will automatically be freed when a method returns. Often C++ needs dynamically allocated objects even when used as a temporary. To use alloca, you would need a smart pointer/RAII and placement new. alloca will not fill the general requirement. Most allocators are binning allocators underneath and will naturally do pooling. If you have some way to coalesce, you will get the least fragmentation. – Oolite

In your answer you have: "First, memory pools are your friend - as the article says" - can you provide a link to the article you're referring to? – Cookshop

From OPs original link in the "Resources for memory management in embedded application" phrase - the one back to another SO article. – Bird

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.

Mcdaniel