Dynamic Memory Allocation in Embedded Apps?

shootTheMessenger asks: "My company is porting our C++ Windows app to C in an embedded device and the question of whether to use dynamic memory allocation continues to come up. So far I have resisted malloc/free use but it gets tedious having the same argument with the next set of managers to take an interest in the project. Is there a definitive answer on the subject, especially one to counter the 'we have plenty of RAM - 16MB - so why not use dynamic allocation' argument? A quick google search finds that some sites frown on allocations within embedded applications, while others say it is OK in some contexts and yet others hack around it with pseudo-static allocations. How do you feel about this particular subject?"

Comments

Take your question...

[HotNeedleOfInquiry]

Over to comp.arch.embedded

Lots of seasoned pros that can give you a good answer.

Is this a Trick Question?

[NullProg]

No one here can answer it without more information. Whats the target platform, Linux, WinCE, QNX? What type of data needs to be accessed? Whats the storage media, DOC, compact flash, hard disk?

You really can't expect to receive a practical answer without giving us more information.

Enjoy,

I think in many situations you have no choice

[WolfWithoutAClause]

I worked on a *big* embedded telecoms project, with about the same amount of memory available; where initially we used dynamic memory as little as possible. Eventually though, we used it almost everywhere, and the places where we hadn't used it were rather awkwardly written and a source of bugs.

I never personally saw it fragment to the point of failure, but another engineer said he had had to debug that situation on this system- a particular sequence of allocation did this once (in many years).

This problem was solved by using a different memory allocator. That was a rare problem on a huge, long lived project.

Overall, I shouldn't sweat it too much, fragmentation causing the memory allocator to fail is rare enough and there are things you can do to solve the problem if it does occur. But you'll need a guru to solve it if it does happen.

Re:Why?

[swillden]

One problem with C++ is that it's difficult to know that an operation always will take the same amount of time.

Absolute nonsense. C++ doesn't have a garbage collector or anything like that running that can introduce random delays. The same bit of code following the same path will take the same amount of time to execute every time... just like C (well, assuming you don't run into cache misses, etc. but those typically don't crop up on embedded processors.).

There can be quite a lot going on in the background whenever you create a new instance of a class, for example, and figuring that out can be almost impossible (especially if things like overloading have been used).

Dead wrong again. If you know the language you can quite easily see what precisely is going to happen. You might have to go read the constructor, and if the class contains other objects you might have to read their constructors, but all of that code is code that would have to be executed in a C implementation as well -- you have to initialize your data somewhere.

C++ does impose some "hidden" costs, but the language is specifically designed to make sure they're insignificant. Virtual function invocations have a hidden cost: An extra pointer dereference, which is dwarfed by the cost of the function call, even if the function is a no-op. If you're going to worry about that cost, you should probably avoid function calls altogether. The biggest potential hit is exceptions. The compiler has to generate extra code in every function to handle cleanup in the event of an exception, and it can cost a bit. In practice, not using exceptions also costs something, because you have to write a lot more manual error handling, which also has to be compiled in, but, in general, stack frames with exception unwinding may add noticeable run-time to functions that don't do much, but do create objects that must be destroyed. If that's a concern, just compile with -f-no-exceptions and write the error-handling code yourself. Some people like to turn off RTTI also, but that's actually very cheap, and it allows for some very clean solutions to complex problems (but use it sparingly, because it's easy to abuse).

The most likely source of apparent non-determinism in C++ code is the same in C code: memory allocation and deallocation. One way to fix that is to get a real-time implementation of malloc()/free(), but even without doing that, C++ provides great tools for making allocation more reliable: by overloading 'new' on key classes and implementing a pooled allocation scheme, you can ensure that allocations and deallocations are both constant-time and faster than any general-purpose allocator could be.

Where C++ is a big win is in the libraries, especially the template libraries. The STL's sort routine, for example, is usually significantly faster than qsort(), and never slower. High-performance, typesafe, THOROUGHLY DEBUGGED collections implementing a variety of different data structures are a big win for any environment (though platforms with very tight constraints on code size may need to avoid them, since they can bloat the binary -- not likely an issue for our friend with 16MB RAM).

For embedded applications (where you frequently must have an upper bound on reaction time) this can be a deal-breaker.

For _hard_real-time_ applications, you mean -- lots of embedded apps are not real-time, much less hard real-time, you're not going to trust C, either. For hard real-time apps what you do is:

1. Pick a processor and platform that has guaranteed maximum instruction times (which means you want to avoid a lot of cache memory and no deep pipelines that may stall badly on a wrong branch prediction).
2. Write your code in a language that compiles to assembler/machine code.
3. Identify the time-critical sections and calculate the cycles that they will consume. (Well, actually you profile first -- it's only necessary to actually count cycles if you're getting close

Re:Why?

[AiY]

First off, I'll just note that all my professional development career has been working with embedded systems.

Second, I'm gonna stay out of the whole "... but <language x> is not an issue because..."

There are many, many reasons to use C instead of C++ on an embedded system. The two biggest are
  a) Portability
  b) Stability/Conformance

C has a much better record of consistency between embedded platforms. It carries little baggage so most vendors get it right. If the same codebase has to run on several platforms, the specific C compiler for each platform probably produces code that behaves more consistently than C++ compilers.

Stability and confromance come from the fact that embedded vendors don't always spend the time keeping their compilers up to date, and you may be forced to used the vendor's compiler.

As a specific case from place of business: A new project was developed entirely on an emulated environment, beautifully done in C++. Object oriented and all that - this fit the project very nicely. The code was quite stable and was continuously tested with a dedicated rig that ran a huge battery of sample cases against the product. Then the port to the first target platform began. Turns out that it wasn't x86 and Microsoft C++ didn't run there. No problem - the vendore had a C++ compiler. But wait - it didn't support complicated features like "templates" so there was fiddling. By the time I saw the codebase, there were two sets of #ifdefs - one for WIN32 (which worked) and one for the platform (which did not). Later we took that code base, stripped out a bunch of features, converted to C and had it running on about 4 different embedded architectures.

Oh, and the low-end platform was a 25MHz 68331 with 2 MB total memory, 1.5MB total that our middleware could use, so effectively about 700 KB. And we used dynamic memory allocation.

The moral: C compilers are simpler so they tend to be better supported. If your team is more comfortable with some other language and the target supports it, go with that. Remember that maintenance will be the major portion so the more obvious the code is to the developers the better.

Take a step back, try something else

[pslam]

My company is porting our C++ Windows app to C in an embedded device

Why would you do that? There's nothing about C++ that rules it out on embedded devices. I smell a bad vendor toolchain. Rule no.1 for sane embedded device development: USE THE GNU TOOLCHAIN. Then you can use C++ and half your porting task is gone. You can use the same toolchain with an x86 target for testing on PCs. You wouldn't happen to be using Green Hills, or god forbid Tasking would you?

So far I have resisted malloc/free use but it gets tedious having the same argument with the next set of managers to take an interest in the project.

Removing dynamic memory management is a noble goal but it goes deep into your coding style, to the extent that you basically end up with forked code instead of portable code - one version for each target inside big #ifs. One nice alternative I've used in the past is a stack separate from the call stack. You can either allocate a fixed size stack using malloc (say, 4MB for a task), or from a fixed location such as on-chip RAM. Allocations are stricly last-alloc'd-first-free'd, which actually fits most usage patterns. The key advantage is you can throw away the entire pool in a single call (pop all), for example when an error occurs, or if you run out of memory. This makes error handling much, much simpler than having a ton of delete's depending on how far you got. It also makes allocation overhead extremely small - it's basically just pointer arithmetic. It's just a souped up "alloca", where the stack isn't the function call stack, so it doesn't go away when the function does.

Best of all, if you use this method you can have a non-embedded version of the "stack" allocator which just uses malloc instead. I've got an example app which does no dynamic memory allocation linked from my profile (it's a Vorbis decoder).

To Dynamically Alloc or Not

[AiY]

Ahh yes, everyone comments with strong opinions without stating important assumptions. The simple answer is "yes, of course you can dynamically alloc memory". The important question not revealed is "why?". Once you have figured out exactly what the memory-related requirements are for you application then you can determine if you need dynamic allocations.

To answer that you need to ask questions like:

Will the app be long-running? If yes, you probably don't want a scheme that will fragment memory because eventually your heap will be too fragmented to allocated necessary contiguous blocks and it will have to reset.

Does the app need to allocate quickly? If yes, then you'll want to avoid allocating at all. Size your buffers ahead of time and never allocate dynamically. Also note that this is not to be confused by with hard real-time requirements. Many real-time applications need only bounded time on operations, so an ordinary allocator would perform very well on average and have known maximums because of bounded initial heap size.

Do you have to supply your own dynamic allocator? If there is an allocator available on the system, that may be the best route.

What are the patterns of your allocations? Does the app allocate many small chunks, a mixture of small and large; are they long lived or short lived? Allocation sizes effect performance and size usage of dynamic allocators.

I'll stop know because I can't think of any other good reasons off-hand. Static allocation is the best thing for many reasons - easy to use, easy to analyze, very fast. That's not practical for all applications, so my advice is to go with a simple allocator next - for C, malloc is good because everyone should know how to use it. Don't worry about speed or efficiency too much - performance usually isn't a problem. Look up "dl_malloc" (Doug Lea's malloc). It's a good public-domain allocator that looks like malloc and works very well allocating small chunks.

Malloc isn't a great fit if your app is constantly running out of space. In that case, find a good garbage collector or memory reordering scheme. Several garbage collectors make life easy by making allocations fast and solving the problem of free'ing memory.

Remember, don't pick an allocation scheme based on the problems you *think* you'll have. Pick an allocator whose major benefit matches your major issue.

Static, if you need reliability

[kbielefe]

If you're going for high standards of reliability like DO-178B certification, then the guidelines are usually to statically allocate as much as possible, use malloc if unavoidable, but never free the memory. This goes contrary to everything they drill into you in college, but it makes the maximum memory usage easily measurable and predictable and also makes the execution time of malloc very consistent. And trust me, you find memory leaks fast.

Yes, it is possible to calculate your memory needs using dynamic allocation and deallocation, but it is a lot harder to prove and a lot easier to make a mistake. If you really can reliably put an upper bound on the amount of memory your app uses, then there is usually no need for dynamic allocation in the first place. If you don't care about predicting your memory usage or malloc execution time, then why are you even asking the question? Just go with whatever is easier. However, consider that some extra effort now will pay off in the long run.

You have to let go of your assumptions from the non-embedded world. The natural instinct is to save as much memory as possible, since your memory is so limited. Your undergrad algorithms class taught you that dynamic allocation is the way to have the lowest possible memory usage at any given time. However, in an embedded application, unallocated memory is just as wasted as extra memory allocated in a static buffer, but in the latter you always know it is available as soon as you need it.

malloc and glibc

[LWATCDR]

The standard way that glibc works is that the heap grows until the task ends. This can cause problems so yes dynamic memory allocation should be avoided but your question leaves out a lot of variables.
1. Does the CPU have an MMU.
2. What OS.
3. Single or multi tasking?

Without knowing more no one can give you a firm answer.