Into, but not out of, the void

C and C++ both use void * as the generic data pointer type, but they treat it differently. Here's some insight into why.

By Dan Saks

Embedded.com

(06/10/08, 12:00:00 AM EDT)

The early dialect of C described by Kernighan and Ritchie (Kernighan, Brian W. and Ritchie, Dennis M., The C Programming Language. Prentice Hall, 1978.) (often called "Classic C") didn't include the keyword void, and therefore had no type void *. Lacking void *, Classic C programs tended to use char * as the type for a "generic" data pointer--a pointer that can point to any data object. Unfortunately, this increased the need to use cast expressions.

For example, Classic C didn't include the now standard memory management functions malloc and free. On page 175 of their book, Kernighan and Ritchie implemented their own allocation function, alloc, which they defined as:

char *alloc(bytes)
unsigned bytes;
{
    ...
}

This function definition is in the old, non-prototyped style of Classic C. In Standard C, the equivalent declaration would be:

char *alloc(unsigned bytes);

This alloc function returns the address of the allocated storage as a pointer of type char *. However, they designed alloc to allocate storage for any type of object, not just char or array of char. When allocating storage for something other than a char (or array thereof), the program must convert the char * result into a pointer to the intended type of the allocated object--a conversion that requires a cast. Kernighan and Ritchie used casts to convert the result of calling alloc to something other than char *, in functions such as:

struct tnode *talloc()
{
   return ((struct tnode *)alloc(sizeof(struct tnode)));
}

The Classic C implementation of free posed a similar problem. Kernighan and Ritchie defined their version of free as:

free(ap)
char *ap
{
    ...
}

Absent the keyword void, they omitted the return type to indicate that the function returns nothing. In truth, the return type defaulted to int. In Standard C, the equivalent declaration would be:

int free(char *ap);

Calling free to deallocate anything other than a char or array of chars required a cast, as in:

int *ip;
...
free((char *)ip);

Standard C eliminated the need for these casts by embracing void * as the generic data pointer type. For any object type T, a C program can convert a T * to or from a void * without using a cast.

For example, Standard C declares malloc and free as:

void *malloc(size_t size);
void free(void *p);

so that for any object type T:

T *p;
...
p = malloc(sizeof(T));
...
free(p);

should compile in C without complaint. No casting needed.

An unfortunate consequence of the C's pointer conversion rules is that they permit accidental conversions between unrelated pointer types. For example:

double *pd;
long *pl;
void *pv;
...
pv = pd;            // compiles in C
...
pl = pv;            // compiles in C

Although pl is declared to point to a long, it now points to a double. Accessing *pl would produce undefined behavior.

C++ reduces the chances of such mishaps by applying slightly more restrictive conversion rules: for any object type T, a C++ program can convert a T * to a void *, but not a void * to a T *. Here's the rationale.

Converting from T * to void * is generally safe because the program can do little harm with a void * object. For example, if pv has type void *, compilers reject attempts to access the object to which pv points. Expressions such as *pv, pv[i], ++pv, and --pv simply don't compile.

Although converting a pointer such as pv from void * to T * (for any non-void T) is itself safe, it throws the door wide open for future unsafe operations, such as accidentally converting an object into something that it really isn't.

Thus, for any (non-void) object type T, C++ requires a cast when converting from void * to T *, as in:

pv = pd;            // compiles in C and C++
...
pl = pv;            // compiles in C, but not in C++
pl = (long *)pv;    // compiles in C and C++

Using a cast enables the code to compile, but doesn't eliminate the undefined behavior. In this case, the cast really is an indicator that the operation is unsafe.

Thanks to Steve Adamczyk of Edison Design Group (www.edg.com) for helping me identify parts of the standard relevant to this discussion.

Dan Saks is president of Saks & Associates, a C/C++ training and consulting company. For more information about Dan Saks, visit his website at www.dansaks.com. Dan also welcomes your feedback: e-mail him at dsaks@wittenberg.edu. For more information about Dan click here .

The yin and yang of dynamic allocation

Despite its risks, dynamic memory allocation is a valuable facility that you shouldn't blindly disregard.

By Dan Saks

Embedded.com

(05/04/08, 01:00:00 PM EDT)

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:¹

• 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:²

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.)³ 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.⁴ 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.⁵ 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.