Dynamic Memory Allocation & Fragmentation in C/C++
In C and C++, it can be very convenient to allocate and de-allocate blocks of memory as and when needed. This is certainly standard practice in both languages and almost unavoidable in C++. However, the handling of such dynamic memory can be problematic and inefficient. For desktop applications, where memory is freely available, these difficulties can be ignored. For embedded - generally real time - applications, ignoring the issues is not an option.
Dynamic memory allocation tends to be non-deterministic; the time taken to allocate memory may not be predictable and the memory pool may become fragmented, resulting in unexpected allocation failures. In this session the problems will be outlined in detail and an approach to deterministic dynamic memory allocation detailed.
What is the main reason the speaker says realloc is problematic for real-time systems?
1) Most RTOSes - if not all - meet these primary criteria. There is no reason why they should not be MISRA compliant. If you have source code, you can verify. A number of RTOSes claim to be compliant anyway.
2) Fragmentation is not possible because there is either an available block or there are no blocks available.
3) I do not know if any, though it would make some sense. However, de-frag would introduce non-detreminism.
4) Why?
5) Doing allocation at start up results in essentially static allocation, which is a very good idea!
Regarding 4: I was just curious. You list the problems/concerns with dynamic memory around 14:51 so I was wondering if "double-freeing a pointer" could maybe also be on that list, since that seems to be a problem unique to dynamic memory.
Regarding 2: Maybe you could help me by defining "fragmentation" and how a block memory scheme prevents it?
If you called free() to deallocate some memory and then called it again, I believe the second call would do nothing.
Fragmentation is when the allocated memory is scattered around the heap, with unused gaps which are no large enough for allocation demands.
Well, fwiw, OWASP (and others) seems to indicate that the result of a double free is undefined, possibly resulting in a security vulnerability. It seems an easy enough thing to check in other implementations of free(), but maybe not something that can be assumed.
- Agree that with pools there can't be fragmentation, but if pools with right or larger block size are full, then you may find yourself in a situation where there would be enough free memory to fulfill the request, but it is allocated for smaller blocks and therefore the request fails. It is not fragmentation, but the effect for the end user is the same.
(And this just remarks the importance of tuning the size of each pool)
Yeah, this is exactly what I was thinking. But I had thought that "fragmentation" is described as the problem that results from an inability to allocate memory despite the heap having sufficient overall space, due to the fact that that space is spread out. It would seem to me that a block memory scheme is still susceptible to that problem (even if it's intentional) and therefore doesn't solve the problem of "fragmentation". If I partition my heap into 1024 blocks of 16 bytes and then make 1024 requests for 1 byte each then I've exhausted my heap despite only using 6% of the available memory; shouldn't that qualify as "fragmentation"? Perhaps a block memory scheme helps limit the amount of fragmentation that could occur, but I'm struggling to see how it eliminates it.
The final effect is indeed the same - despite counting a grand total of enough free memory, the system can't fulfill the allocation request for how the free memory is organized.
Fragmentation refers to a condition in which free memory is fragmented and interspersed with in-use memory. This condition is not possible when using pools as described by Colin.
Though there is no magic wand to solve dynamic allocation :-) . Pools need to be carefully designed (and tuned) both to limit the case you describe (slack space at the end of a block) and the case I described (wrong dimension of pools with respect to the use).
- In Windows 3.0 / 3.1 (and possibly earlier versions) the allocation function (GlobalAlloc/LocalAlloc) returns a handle. In order to access the allocated memory you need to Lock the handle and Unlock it when done. This allows the system to move memory around when it is not locked by any process. BTW if you needed memory to stay fixed a dedicated flag was available in the allocation function.
Is there a library, tool or example technique that will help developers visualize the heap fragmentation in a dynamic execution environment? For example, is there a heap profiler that can run alongside the application that will show the state over the heap every 10 ms or every period that's configurable?
I am not familiar with such a tool. I guess it would need to be run as a separate task or timer tick interrupt service routine.
Oh, also I had read on Embedded Artistry about stack protections offered by GCC and Clang and thought I'd post a link for others.
Thanks for the great talk, Colin! I have a few thoughts/questions for you about it: