The yin and yang of dynamic allocation - Embedded.com

The yin and yang of dynamic allocation

A few months back, I explained that each object in C and C++ has one of the following three storage durations: static, automatic, and dynamic:1

• An object with static storage duration has storage that is allocated at program startup and remains allocated at the same location until the program terminates.

• An object with automatic storage duration has storage that's allocated upon entry into a block (typically a function body) and deallocated upon exit from that block.

• An object with dynamic storage duration has storage that's allocated when the program calls an allocation function, such as malloc in C or an operator new in C++. The object's storage lasts until the program passes the address of that object to a corresponding deallocation function, such as free in C or an operator delete in C++.

While it's nearly impossible to write a useful program without using both static and automatic allocation, programs can–and do–manage to get by without any dynamic allocation. This month, I'll look at the case for and against using dynamic allocation.

Quick takes
Static storage allocation typically has no run-time cost. The initialization of statically allocated objects may take place at run time, but the allocation itself usually takes no time. (Of course, the allocation still takes up memory space.) Unfortunately, in applications that juggle diverse collections of objects, big and small, using static storage squanders memory and imposes rather arbitrary restrictions on program behavior.

For example, suppose your application uses two different-sized regions of memory, say, buffers and blocks. Your target system might have enough memory to statically allocate 100 buffers or 250 blocks. Should you carve up space for 50 buffers and 125 blocks, or is a typical application more likely to need up to 60 buffers but only 100 blocks? And what about those occasions when program needs 80 buffers but only 50 blocks? Tough luck?

The run-time cost of automatic storage allocation is usually pretty low–often only an instruction or two on each function entry and exit. On microcontrollers with limited stack space, the cost can be higher. Automatic storage uses memory very efficiently, but it's useless for objects with lifetimes that persist beyond function calls.

By comparison, dynamic storage allocation is much slower than either static or automatic allocation. A call to malloc (in C or C++) or operator new (in C++) may execute tens and occasionally hundreds of instructions in a quest for storage of the requested size. Deallocating storage by calling free (in C or C++) or operator delete (in C++) often requires comparable effort.

You do get something for that effort: dynamic storage allocation uses memory much more flexibly than static storage allocation. Using dynamic storage may add a little overhead to the storage for each object, so instead of 100 statically allocated buffers, you might have room for only 99 or 98 dynamically allocated buffers. But now any run of the program can have up to 98 buffers and no blocks, or up to 123 blocks and no buffers, or any balance of buffers and blocks within those limits that doesn't exceed total available memory.

Risky business
Dynamic memory allocation brings with it a number of risks. Some developers, especially for embedded systems, find these risks too great to accept and follow the advice of the MISRA-C guidelines. (MISRA is the Motor Industry Software Reliability Association in the UK). According to their guidelines:2

Rule 20.4 (required): Dynamic heap memory allocation shall not be used.

This precludes the use of the functions calloc , malloc , realloc , and free .

There is a whole range of unspecified, undefined and implementation-defined behaviour associated with dynamic memory allocation, as well as a number of other potential pitfalls. Dynamic heap memory allocation may lead to memory leaks, data inconsistency, memory exhaustion, non-deterministic behaviour.

Although I have some quibbles with the wording, it covers most of the major concerns. These concerns also apply to operator new and operator delete in C++. Let's look at them (and my quibbles) in some detail.

Undefined behavior is what a program exhibits when it does something erroneous that the compiler and run-time system need not detect (often because they just can't). For example, freeing a pointer to storage that's already been freed, or that never was allocated, produces undefined behavior. The undefined behavior typically corrupts the heap–the data structures that support the dynamic memory. The corruption in the heap usually spills over into other data and run-time structures, and the program eventually crashes.

Implementation-defined and unspecified behaviors are behaviors of correct programs that may vary with different platforms. The difference between implementation-defined behavior and unspecified behavior is simply that each compiler must document its implementation-defined behaviors but not its unspecified behaviors. (You can find more about undefined, unspecified, and implementation-behaviors in a column I wrote several years ago.)3 For example, when a program calls malloc to request zero bytes, the return value of the call is implementation-defined. It might be a null pointer, or it might actually point to allocated storage. If it does point to storage, the amount of that storage is unspecified.

In a sense, memory leaks are not really a problem. Memory exhaustion is. A leak here or there doesn't really cause any harm. The accumulation of many leaks over time becomes a problem when it exhausts available memory and deprives the program of resources it can't survive without. Listing memory leaks and memory exhaustion as separate ills may be redundant.

I'm not sure what the MISRA guideline means by data inconsistency. I looked it up online and found no consistent usage. Some articles use it as another term for heap corruption. Others use it to describe the corruption of values in individual dynamically allocated objects. Whatever data inconsistency is, it's probably just another manifestation of undefined behavior, and I'm not sure it deserves special mention.

Common implementations of malloc and operator new have nondeterministic behavior. That is, the execution time of an allocation request can vary, sometimes markedly, with the size of the request and the current state of the heap. This nondeterministic behavior poses serious problems in real-time systems that require reliable upper bounds on the duration of certain events.

If you've never seen how malloc and free are implemented, take a look at Chapter 8 of Kernighan and Ritchie's classic introduction to C.4 They present a complete, working implementation of malloc and free . It's less than five pages of code and prose, and well worth the time to read.

Many real-time operating systems (RTOSes) offer alternatives to the standard malloc and free that allocate and free fixed-sized blocks from a larger, user-provided memory region, often called a pool . Writing pool-based allocation functions with short, deterministic execution times is a fairly easy thing to do.

The MISRA guideline failed to mention fragmentation, and maybe it should have. Fragmentation is what you get after many allocations and deallocations for different-sized chunks of storage leave many odd-sized chunks in the heap that the program can't seem to use. Depending on the allocation scheme, fragmentation might increase allocation times and thus degrade run-time performance. It can also lead to memory exhaustion. Using pool-based allocation schemes often reduces fragmentation.

Still worth a look
Despite these potential hazards, some problems are just much easier to solve with dynamic memory allocation rather than static allocation, so you shouldn't dismiss dynamic allocation out of hand. Some systems manage to use dynamic memory in limited ways that accrue some benefits without taking on unacceptable risks. One approach is to use dynamic allocation to acquire resources only during program startup. This allows the application greater freedom to allocate memory to objects as needed, but avoids problems with fragmentation, leaks, and nondeterminism during steady-state execution.

Understanding the ins and outs of dynamic memory allocation is especially worthwhile for C++ programmers. C++ offers many facilities–most notably classes with constructors and destructors–that dramatically diminish the incidence of memory leaks. C++ also lets you define an operator new for each class, providing a convenient and efficient packaging for deterministic, fixed-sized allocation schemes. You can even use operator new to place device registers in memory-mapped locations, as I did in a recent project.

I'll delve more into dynamic memory allocation in the coming months.

A correction
In my March column on linkage, Table 2 summarized how C and C++ determine linkage and storage duration for an object from the storage class specifier and the scope of the object's declaration.5 The entry for objects declared at class scope with the storage class specifier static (usually known as static data members) erroneously indicated they have internal linkage. They actually have external linkage.

Endnotes:
1. Saks, Dan, “Storage class specifiers and storage duration,” Embedded Systems Design , January, 2008, p. 9.

2. MISRA-C 2004: Guidelines for the use of the C language in critical systems. Motor Industry Research Association, October 2004.

3. Saks, Dan, “As Precise as Possible,” Embedded Systems Programming , April, 2002, p. 43 .

4. Kernighan, Brian W. and Ritchie, Dennis M., The C Programming Language, 2nd. ed. Prentice Hall, 1988.

5. Saks, Dan, “Linkage in C and C++,” Embedded Systems Design , March, 2008, p. 9.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.