Robert Ward is president of R&D Publications, Inc. and author of Debugging C, an introduction to scientific debugging. He has done consulting work in software engineering and data communications and holds an M.S.C.S. from the University of Kansas.
While modern debuggers like CodeView and Turbo Debugger supply at least some minimal tools for dealing with most types of bugs, neither supply any meaningful facilities for finding bugs affecting the heap. Fortunately, you can build some very effective heap instrumentation with only a few lines of code. Moreover, using some simple pre-processor tricks, you can retrofit existing code with this instrumentation.
Heap bugs fall into two general classes: sequencing errors and pointer damage. Both kinds of bugs can potentially cause hidden damage to the heap's internal structure, damage that may not become visible until thousands of lines of code later. Such delayed-symptom bugs are very difficult to trace to their causes using the built-in tools in typical breakpoint debuggers.
In this article, I'll show you how to use the preprocessor to attach instrumentation to the heap allocation and deallocation functions. This instrumentation, used together with a sort utility, can quickly and easily identify sequencing errors in even large and complex programs. In addition to identifying sequencing errors, the instrumentation will generate the information you need to quickly identify the cause of the error (using your breakpoint debugger). Later, I'll suggest ways you can enhance the general framework to add protection against freeing a damaged dynamic object.
The tools presented here, however, won't be of any help if you have a pointer bug that is directly writing on the free list. The heapwalk function supplied with your compiler is your tool of choice in that situation.
Sequencing Errors
By sequencing errors, I mean bugs created by incorrectly allocating or freeing dynamic memory. An example is attempting to free an object that wasn't created through a call to calloc or malloc. Another is failing to free an object before allowing its pointer to go out of scope, or attempting to free an object that hasn't yet been allocated.The standard free supplied with many compilers fails to detect even the most common sequence errors, and instead blindly links some piece of garbage into the heap, potentially causing malloc to get very confused when it later attempts to create new objects from this garbage space. Unfortunately the corresponding malloc function is seldom intelligent enough to know it is confused. malloc assumes all is well and builds the requested object — but it may build the new object from heap space already used by some other active object, or from space on the stack, or from space in static memory.
While sequencing errors are generated by errors in program logic, they frequently result in symptoms that appear to be completely unrelated to the program's logic. For example, if you accidently free a local variable, your program might run normally until some subordinate subroutine attempts to return. If you fail to free some dynamic object, the program will probably run correctly for long periods of time and then suddenly fail when it can no longer allocate new objects.
In all cases, you are not guaranteed any visible cause-and-effect relationship between the erroneous code and the visible symptoms.
While you can locate sequence errors by meticulously tracing and validating every dynamic memory operation in your program, only masochists would want to do so. Single-stepping and other kinds of tracing can be effective methods when you have some clues about where to find the cause. In this instance, your only clue is that the error involves some call to malloc or free, somewhere in your program.
Pointer Damage
Because the heap is simply a data structure (albeit, one initialized by the system instead of by your application code), it too can be damaged by attempts to write or copy through an invalid pointer. Unallocated portions of the heap are linked into a "free list." If a pointer operation should overwrite one of the nodes in this list, the list will be corrupted. Allocated objects also contain hidden bookkeeping information that allows free to efficiently return the object to the free list. If this hidden information is overwritten, free will corrupt the free list when it tries to deallocate the object.
Sequence Invariants
It's simple to write a set of rules that identify correctly sequenced dynamic memory operations:
These rules are always true (invariant) for every correct dynamic memory operation. Whenever you can describe correct behavior with simple rules like these, you should look for a way to automate exception detection. When you do, you've automated some of your debugging effort.
- Every unique object is allocated exactly once.
- Every unique object is freed exactly once.
- An object is allocated before it is freed.
To detect exceptions to these rules, you must generate for each dynamic memory operation a record of what object was involved and what operation was performed. I enforce this record keeping by wrapping the real calls to malloc and free in a "debugging wrapper." (See Listing 1. ) Using the preprocessor, I redefine malloc and free everywhere except within this wrapper. The redefined calls invoke the wrapper function which then invokes the real function.
Each wrapper function writes a record in a debugging log file on each call. The malloc function writes a record consisting of the pointer to the new object, the word "anew" (chosen, like the 99999, to force the "new" record to sort before the "free" record) and the serial number assigned to this instance. The free wrapper reports the pointer value and the word "free."
To add this instrumentation to any program, you merely #include Listing 1 in every file that performs calls to malloc or free and #define the preprocessor variable DEBUG, as illustrated in Listing 3. The #include should appear early in the program, but since the header defines all its own data (and even opens its own files on demand), you have considerable latitude in the exact placement.
Listing 3 is a simple tree sort, structured as a filter, complete with two intentional errors. If you need a sort utility and don't care about high performance, you can remove the lines marked /* error */ and recompile. In Listing 3, I've defined DEBUG in the code. If instead you define DEBUG on the compiler command line, you can generate both test and production versions of your code without editing the file.
The reported pointer value together with the serial number uniquely identify each allocated object. Unfortunately, with this implementation, the serial number is no longer available when the object is freed — so the object cannot be uniquely identified when it is freed (two dynamic objects might have used the same heap space at different times). Some programs (Listing 3, for example) always use dynamic objects in a FIFO pattern. For such programs, the simple wrapper of Listing 1 is adequate.
Other programs will require a more complex wrapper, one that not only inserts information-logging code, but that also modifies the structure of the dynamic object. The malloc wrapper in Listing 2 requests a block of memory larger than that needed by the application, inserts the serial number at the beginning of the allocated block, and then returns a pointer to space following the serial number (see Figure 1) . The serial number will now be available to the free wrapper, but is hidden from the application. The application thinks the pointer it receives points to the beginning of the allocated object. In fact, the application receives a pointer that points to just after the start of the allocated object, but since the object is now larger than expected, the deceit is harmless.
The application will invoke free with the same offset pointer. The free wrapper will use pointer arithmetic to back up to the true start of the object and use that corrected pointer to invoke the standard free function.
Additionally, to make it easier to identify particular free operations, I have added a separate counter for calls to free. This second "serial number" is printed to the right of the word "free" in the log entry.
With this enhancement, both wrappers can know and report the allocation serial number, guaranteeing a unique object identifier for both free and malloc operations.
Detecting Exceptions
Running the sort program of Listing 3 with the simple form of logging enabled produced the log file in Listing 4. I used a correct sorting program to produce the sorted file in Listing 5. For a short file, sorting is enough to make the sequencing errors obvious. For more complex runs, producing very long log files, sorting isn't enough. The program in Listing 6 is a small state machine (see Figure 2) that operates as a filter. Its input is a sorted log file, its output is a list of sequencing errors. I created the test data in Listing 7 by editing the log file from a normal run with the enhanced logging enabled. Listing 8 shows the result of feeding this test file to the exception filter.
Finding The Bug
These three pieces (instrumentation wrappers, sort utility, exception filter) will tell you if your program commits a sequencing error — they won't tell you what part of the program commits the error. However, you can use the serial numbers of the object and the free call together with your breakpoint debugger to find the code involved.First, you must be able to control input well enough to exactly replicate the run that produced the log file. Exact replication will be easiest if you can redirect input from a file. If you can't, consider using the wrapper technique to add "debugging input" capabilities to the low-level input routines.
Once you can replicate a run that includes a sequencing error, load the application under the debugger and set a breakpoint at the beginning of malloc. Use the reported serial number to set a passcount for this breakpoint. Start the application. It should stop on the malloc call that creates the object involved. Using a stack traceback and other browsing tools, you should be able to identify the calling context. If the sequencing error involved an improper free, you would follow the same process, but set the breakpoint at the beginning of free and use the free serial number as the pass count.
Adding Fenceposts
The malloc function hides heap-related information in front of the pointer to each dynamic object — just as my instrumentation wrappers do. If an errant pointer writes over this information, the heap will be corrupted when the object is freed. Since dynamic objects are physically adjacent to one another in memory, damage to the hidden information in one dynamic object is usually the result of writing beyond the end of some other dynamic object.In Listing 9, I've modified the malloc wrapper so that it adds some padding to the end of the object as well as the beginning. The malloc wrapper stores an infrequently used pattern (a signature word) in this trailing space, creating a fencepost. Now the program can't write beyond the end of the object without destroying the signature. The free wrapper checks the signature word and reports any change. Note that the leading pad has been expanded to include size information. The free wrapper must know the size of the object to know where to look for the fencepost. If the fencepost has been overwritten, the free wrapper will write a "damaged object" message in the log. Figure 3 shows the new object structure.
If you know enough about your compiler's heap mechanism, you can avoid storing the size. The standard heap routine is already storing size information somewhere in the dynamic object — you just need to figure out how to access it. I prefer this redundant method because it's easier to understand and adapt to different compilers.
Caveats
My wrappers assume that every dynamic object is created with malloc. If your program uses realloc or calloc you will need to create separate wrappers (and separate serial number statics) for those functions. Also, since the wrappers replace function calls with macro calls, they may break existing code that has side-effects in the arguments to the malloc or free calls. (However, the nature of these functions would naturally discourage such usage).All code presented here was tested with Turbo Debugger in small model. For other models and compilers, you may need to modify the pointer arithmetic in the wrappers.
Conclusions
This set of tools isn't subtle, complex, or particularly original, but when used in combination with a breakpoint debugger, they make heap problems relatively easy to find.More important, the techniques and ideas used in this package transport to many debugging problems. Instrumentation wrappers can often be used to attach debugging code to critical functions. Serial numbers are useful anytime you are debugging dynamic data structures. Fenceposts can even be inserted between static data elements and used to detect out-of-range writes.
Effective debugging, like effective programming, depends upon mastering a range of tools and applying them in appropriate combinations.