memmgr – a fixed-pool memory allocator
October 17th, 2008 at 12:44 pmIn embedded systems, it is common to write code that runs on “bare metal”, i.e. without an operating system. On one hand, it is very empowering. When you write your main function (assuming it’s C, of course, but that’s a safe assumption for 95% of embedded code), you know it has the full control of the processor. Your program is the brains of the chip – whatever you write, the chip performs, without any external code getting in your way.
On the other hand, code running this way misses many of the benefits operating systems provide. Process control, memory management, file system, and so on.
When writing code to run on bare metal, there are some special precautions one must take. One important point to consider is the heap – dynamic memory allocation. An embedded system (think of the safety controller of a Boeing plane) can’t just fail because the heap runs out. When malloc returns 0 to your desktop-application code, in most cases you will just bail out, because most probably it’s the system’s fault, and you don’t have much choice. In an embedded controller, this is not an option. There is nowhere to bail out to, and in any case, that heap memory ran out is your fault, a bug in your design or code.
To help managing these complications, embedded programmers often avoid heap allocation altogether, and only use static allocation (i.e. arrays allocated at compile (or more accurately – link/load) time). However, sometimes this is less than optimal, because:
- Dynamic allocation helps write code in a more convenient and reusable way.
- You may be using some 3rd party code that uses dynamic allocation
The solutions to this problem are numerous, but as any self-respecting embedded programmer, I wrote my own fixed-pool memory allocator. It provides a pair of functions:
// 'malloc' clone
//
void* memmgr_alloc(ulong nbytes);
// 'free' clone
//
void memmgr_free(void* ap);
That can be used as a drop-in replacement for malloc and free, but with a twist. There is no heap involved. All the memory is allocated from, and returned to, a fixed pool of memory that’s allocated at link time (in simpler terms: a static array). This way, you know the maximal amount of space your heap will take even before running the program, and can use these functions to test that your program indeed doesn’t allocate more than you assumed.
Moreover, the library allows a printout of allocation statistics (which you can enhance, the code is open) that will help diagnose allocation problems and memory leaks.
The library (350 LOC of ANSI C) can be downloaded from here. Let me know if you’ve found it useful.
Related posts:
October 17th, 2008 at 18:19
Sorry, but I really don’t understand how your implementation differs from a standard memory heap, or what does it solve. Is it the ability to configure a heap size? I think this is a standard feature in most memory managers.
A memory manager that I used (back in my C days) had the nice feature that wrote into each memory block (in #DEBUG) a unique ID (hashcode) of the filename & line number in which it was allocated. Then, at the end of the program, we could immediately spot where memory leaks originated. Another cool feature we used was the ability to have specific/random memory allocations fail deliberately, and test how the application code deals with these failures.
Also, it might be useful to include magic numbers at the beginning and/or end of the allocated blocks, and verify these on free(). God, I’m glad I’m programming in a language with garbage collection and no direct memory manipulation – life is so much easier.
October 17th, 2008 at 18:58
I wanted to simulate my embedded code for testing (even on a PC) and be absolutely sure about how much memory it consumes. It depends on the compiler how the heap is managed. Usually, the stack grows down and the heap grows up towards it, and there’s no real way to find out when they’ll clash.
It’s just simpler this way than by tweaking obscure compiler flags that you can’t be really sure even work because no one really uses them.
October 17th, 2008 at 23:53
I’ve worked on various embedded avionics systems for Boeing planes and I’m skeptical. Let’s take the fragmentation issue.
You have a system that never has more than say 3,000 bytes allocated. But the system allocates 1,000 bytes, then allocates the next 20 contiguous bytes, grabs the next 1,000
bytes, releases the 20 bytes, then asks for 1,000 more bytes. Sure you have 1,000 available,
but they are split between a 20 byte group and a 980 byte group. Trying to create the thousand byte hole you need is problemetical because of real time issues if you try to
move bytes around plus the problem of finding all the references to the block you’re moving.
One approach that works is to allow only a fixed set of allocation sizes and allocates each specific size to it’s own static array.
October 18th, 2008 at 01:20
James,
As you surely know, there are a lot of ways to handle this problem. Memory managers can be made as complex as one desires. The simplish manager I uploaded supports reclamation of adjacent free blocks, uniting them into larger blocks.
But yes, I’m aware of the fixed set of allocation sizes strategy. Indeed, not only it’s good against fragmentation, it also allows for a simpler and faster memory manager.
October 18th, 2008 at 03:17
You can certainly make memory managers as complex as you want. Complexity is not necessarily a good idea in embedded systems.
October 18th, 2008 at 13:27
Yet, surely this is a solved problem, I would imagine…
May 10th, 2009 at 07:44
Nice post. Very interesting. I agree with james. Complex memory manager are not good for embedded systems. But the fixed pool memory allocator is useful too. depending on the situation.
June 8th, 2009 at 07:51
Allocating memory from a fixed memory pool is very fast and, more importantly, deterministic. However the size of each allocation is fixed at the time the pool is created. This is not a problem if the required allocations are all the same size, or nearly so, but otherwise the memory will be used inefficiently. The pool cannot become fragmented.
So depending on the situation we should select which one suites us the most.
July 11th, 2009 at 13:38
I totally agree with the earlier two comments. Allocating from a fixed memory pool is faster. But there are occasions we can’t use it. So it all depends on the situation.
August 19th, 2009 at 12:36
That’s a really cool ti[. Just the exact tool I was looking for. Thanks a bunch for the tip. Appreciate. Cheers