embedded software boot camp

Free store is not free lunch

Friday, January 29th, 2010 by

In my previous post “A Heap of Problems” I have compiled a list of problems the free store (heap) can cause in real-time embedded (RTE) systems. This was quite a litany, although I didn’t even touch the more subtle problems yet (for example, the C++ exception handling mechanism can cause memory leaks when a thrown exception bypasses memory de-allocation).

But even though the free store is definitely not a free lunch, getting by without the heap is certainly easier said than done. In C, you will have to rethink implementations that use lists, trees, and other dynamic data structures. You’ll also have to severely limit your choice of the third-party libraries and legacy code you want to reuse (especially if you borrow code designed for the desktop). In C++, the implications are even more serious because the object-oriented nature of C++ applications results in much more intensive dynamic-memory use than in applications using procedural techniques. For example, most standard C++ libraries (e.g., STL, Boost, etc.) requrie the heap. Without it, C++ simply does not feel like the same language.

Here are a few common sense guidelines for dealing with the heap:

1. For smaller systems, such as microcontrollers with only on-chip RAM, you probably don’t want to open the heap can of worms at all. The problems and waste that goes with the heap aren’t simply worth the trouble.

For systems with sufficient RAM, such as processors with megabytes of external DRAM, trading some of this cheap RAM for convenience in programming might be a reasonable deal. In the following discussion I assume that the system is big enough to run under a preemptive RTOS.

2. The simplest option is to limit the use of the heap to just one task. In this case, heap is not being shared concurrently and does not need any mutual-exclusion protection mechanism. To limit the non-determinism of the heap, I would recommend assigning low priority to the task that uses the heap. The priority should be lower than any real-time task.

3. At the expense of introducing a mutual protection to *all* heap operations (e.g., a mutex), you can allow more than one task to use the heap. However, I would still strongly recommend against using the heap in any tasks with real-time deadlines. All tasks that use the heap should run at a lower priority than any of the real-time tasks.

4. In any case, heap should never be used inside the interrupt service routines (ISRs).

In summary, using the heap in real-time embedded (RTE) systems always requires extra thought and discipline. You should always make sure that the heap is correctly integrated with your runtime environment.

5 Responses to “Free store is not free lunch”

  1. Tad huskie says:

    Right, regarding no 4., I used to meet this issue. Once as in writing some code into a pic, I tried putting code into an interrupt service routine, the result in simulator informs that so lots of stack overflow and underflow, I hadn’t figured it out until moving all code out of ISR, just using some bit as flags in that, and it did really work. So as a rule of thumb, ISR is very sensitive, as little code using the heap as possible!

  2. John Wellbelove says:

    “For example, most standard C++ libraries (e.g., STL, Boost, etc.) requrie the heap. Without it, C++ simply does not feel like the same language.”

    It’s possible to create alternate allocators for STL. I recently published an article on Codeguru decribing an allocator that takes its resources from the stack, so that STL containers can be used as local variables in functions, without touching the heap at all.

  3. Apart from the timing uncertainty inherent in using a heap, there is the issue of fragmentation, leading, effectively, to a progressive reduction in the total memory available for allocation. This is a *very important consideration* in most embedded systems and, as usual, it has been ignored.

    As John has hinted, it is possible to provide alternative allocation strategies in C++, but this is not just about STL (which I hate, anyway). It is possible to eliminate the heap entirely and to provide per-class pools for those ob jects which are to be allocated dynamically. These, having fixed-size blocks, are immune to fragmentation. Furthermore, fixing the pool sizes at design time and attaching each pool to a specific class limits the scope of memory starvation problems and allows them to be found and fixed more easily. The space overhead for each pool is very low and timings are fast and determinate.

    Maybe it sounds hard to do all this. Well, designing the necessary templates, etc., took me some time, but they are very easy to use (by simple inheritance) and completely transparent in operation (just use “new” and “delete”, as before).

    I’ve been quite evangelical about this subject on my blog (link available on the home page of this blog), and my code is available there for download via the “subscribers” page. There’s a new, better documented version on its way quite soon. Any comments on my viewpoint – either here or there – greatly appreciated.

    • Actually, fragmentation was acknowledged as a problem in Miro’s previous post: “A Heap of Problems”, so my assertion that it had been ignored applies only to this article, which is a bit parochial of me. Sorry about that!

  4. Since my last post I have been working on a template library specifically tailored for embedded systems.
    It includes a set of STL like containers which store their elements in contiguous memory pools, the size of which is allocated, per container, at compile time.

    http://www.etlcpp.com

Leave a Reply