Automated Memory Checking in C

Zlatko Marcok

If you know the physical layout of your system's memory, you can verify its integrity automatically. Here's how.

Introduction

Memory management poses problems for even experienced programmers. Memory leaks, writing past allocated bounds, and incorrect releasing of memory can make a program perform unpredictably. Some languages, such as Java, are based on the premise that the problem is too complex for programmers and should be handled at the system level. In C, where efficiency is paramount, the programmer takes responsibility for memory management. C programmers can find help through commercially available tools or build extra monitoring code around the standard memory functions. The extra code records information about memory allocations and ensures that memory is used properly. If you are fortunate enough to work on a project in its initial phases, you can call your custom memory allocation functions directly. If you already have a large existing code base, you can still take advantage of your custom memory management functions with only minor source-code changes. All you need is a cooperative C preprocessor. This article presents a technique, called the memtrack library, for linking custom memory functions into a large project. The memtrack library will notify you of the following with a high degree of certainty:

This article is applicable to all Unix systems. However, some of the information is specific to DEC Unix and the DEC Alpha architecture. In particular, to detect memory leaks, you must know where to look for memory references, so you must know how a program is laid out in the OS-specific virtual memory. Hopefully, I have presented enough background to enable you to fill in your own OS-specific information.

Memory in a Unix Program

A program in a Unix system is divided into the following segments [1]:

Typically, the stack and heap are at opposite ends of an address space. On the DEC Alpha, a process in virtual memory is organized from low to high addresses in the following order: stack, text, data, BSS, and heap [2]. The variables providing the addresses of the segment boundaries are documented in the Unix section 3 man page entitled end, and the section 2 man page entitled brk. The locations of interest are the start of the text segment (&_ftext), the start of the initialized data region (&_fdata), the start of the heap (&_end), and the end of the heap (sbrk(0)).

Implementation

To provide the required diagnostic information, the memtrack library records the filename and line number from which a memory allocation function is called. On a large established project, it is impractical to change all the function calls to provide this information. The solution is possible with the C preprocessor. When the compiler is invoked, the -D option is used to define replacements in source code. For example, if you specify -Dmalloc=MEMTRACK_MALLOC, all instances of malloc will be replaced with MEMTRACK_MALLOC. In memtrack.h (Listing 1), MEMTRACK_MALLOC(size) is defined as memtrackMalloc(size, __FILE__, __LINE__), providing the filename and line number to memtrackMalloc. memtrackMalloc executes the Standard C malloc and returns the result. This idea is extended to calloc, realloc, valloc, strdup, strcpy, strcat, and free. The definitions are undone within memtrack.c (available for download from <www.cuj.com/code>), allowing the Standard C versions of the functions to be called from there.

The memtrack library maintains a dynamic array, memList, of allocation record (AllocRec) structures. When memory is allocated, an allocation record is created and appended to memList. When memory is freed, the record is overwritten with the last memList item. This keeps the array packed with minimal overhead for insertions and deletions. memList grows or shrinks as needed in increments of MEMLIST_CHUNK (defined as 512) elements. The variables memListAllocated and memListConsumed record how much free space is available.

When a request is made to use allocated memory, memList is searched for the allocation record to validate the request. If an allocation record cannot be found or the pointer is suspect, a warning message is displayed, but the operation continues as requested, giving the caller the benefit of the doubt. memList may be out of sync with reality if libraries not compiled with the memtrack definitions release memory allocated through memtrack. This is rare; typically, the allocation and release of memory is done from the same module. In my experience, the warnings have always indicated an error in programming. In cases where a pointer is invalid, such as a non-heap space being freed, the operation is not done, and an error message is printed.

Each allocation request made through the memtrack library actually allocates one element more than was requested. The extra element at the end stores a one-byte sentinel, defined by END_SENTINEL. The library periodically checks the sentinels of all allocations, to ensure that memory has not been written past its allocated bounds.

When memory is freed, it is filled with FREED_FLAG, a printable character, to make freed memory usage more visible. Memory is freed by memtrackFree. The function checks for a non-heap pointer (i.e., one out of the heap range). If the pointer seems good, the function searches for the allocation record using memList_remove, which removes the record from memList and returns a copy of it. If the allocation record is not found, the function uses memList_findInRange to check if the pointer being freed refers to within some allocated block. This may be a programming error and a warning message is printed. If no allocation block can be found, memtrackFree checks for FREED_FLAG at the pointer. The presence of the flag may indicate that the memory has already been freed and causes a warning message.

The memtrack versions of malloc, calloc, valloc, and strdup are straightforward because they deal with the request for new memory; the memtrackRealloc function is more complicated. The realloc function is typically used to reallocate previously allocated memory, copying the contents of the old memory location to the new location. However, if it is called with NULL, it functions as malloc, and if it is called with 0 as the new size, it functions as free. The first thing memtrackRealloc does is determine how it is called and delegates the work to memtrackFree or memtrackMalloc if required. It searches for an allocation record and performs the same validation checks as memtrackFree: checking that the pointer has not been freed and that it refers to the start of an allocated region.

Detecting Memory Overrun

Most versions of the malloc family allocate more memory than requested, using the extra memory for record keeping. Writing beyond allocated bounds can corrupt these records and other program data, causing an abort or invalid behavior. Such problems are hard to diagnose because they are intermittent and the symptoms are usually far removed from the cause. Memory overrun can occur whenever a pointer is used to write to memory, so it cannot always be caught as it occurs, but it can be caught when done through a function. The functions strcpy and strcat are particularly susceptible to overrun because they don't have an explicit length parameter. The memtrack library redefines these two functions so that the destination size is passed to the functions with the source and destination parameters. The sizeof operator calculates the destination size during compilation. If the destination happens to be an array, sizeof will evaluate to the length of the array. In this way, the code:

char d[32]; strcpy(d,"abc");
becomes:

char d[32];
memtrackStrcpy(d,"abc",32,f.c,1);
If sizeof(destination) equals sizeof(char*), the destination is assumed to be a pointer, and its allocation record is searched for in memList. With the allocation record, the functions determine the space available for the operation -- keeping in mind that the memory size recorded in the allocation block must accommodate the END_SENTINEL. The memtrack versions of strcpy and strcat will fulfill the request up to the valid end of the destination, if it can be determined. They will not allow a memory overrun and will print a warning message if one is attempted. If no allocation record is found, the string operation is performed silently. Other functions that could be redefined in this way are memcpy, memccpy, memset, memmove, bcopy, and bzero.

The memtrackCheckSentinels function checks that all allocated blocks have the END_SENTINEL byte in place. This function produces an error message, stating the point of allocation, for each block missing END_SENTINEL.

Detecting Memory Leaks

Memory leaks are divided into two categories -- leaks and potential leaks. In this implementation, a leak occurs when no memory location available to the process contains a reference to the allocated block. A potential leak occurs when the only reference to an allocated block points to within the block. Potential leaks usually become real leaks, or -- even worse -- invalid calls to free. The memtrackCheckLeaks function detects leaks by examining each writeable location of the program, interpreting its value as a candidate pointer, and searching for an allocation record corresponding to the pointer. Each allocation record found is marked as having either a reference to the start of or to within its allocated block, as the case may be. For efficiency, the lowAddress and highAddress variables represent the address extremes of allocated memory. Candidate pointers outside this range are not searched for in memList. When all the writeable locations have been examined, the allocation records are checked. Those having no references marked are displayed as leaks, and those having only references to within their allocated blocks are displayed as potential leaks.

Candidate pointers are obtained by searching the stack, heap area, environment area, and optionally, the machine integer registers. Checking machine registers is the most problematic and least critical. Each processor has its own specific number of general-purpose integer registers, and each compiler seems to have its own syntax for embedded assembler code. The source code available at <www.cuj.com/code> shows the method for a DEC Alpha architecture using the DEC cc compiler. Using the DEC cc compiler, the syntax asm("mov $1, %v0) will move the value in register 1 to the return register (%v0) where it can be picked up as a return value by C. This is done for each register, resulting in a register snapshot. It is necessary to take a snapshot before making any search through memList since the search itself will cause memList addresses to be placed into the registers. Don't be concerned if you cannot read the registers on your machine. I've run the implementation without the register checking with no loss in effectiveness.

The stack is searched from the current frame, up to the start of the program text segment (&_ftext). The current stack-frame address is roughly the address of a local variable in the memtrackCheckLeaks function. The remaining address space is checked from the start of the initialized data region (&_fdata), to the end of the heap (sbrk(0)). Naturally, the memory containing memList itself is bypassed, since it has references to all allocated memory. Finally, the environment area is searched. The environment area (see man environ(5)) is an array of strings that may be modified by a program through the setenv function call. A program may pass allocated memory to setenv, so the environment area must be checked to prevent false leak reports.

memtrack will not catch all leaks. It is not possible to determine if a value in memory that looks like a pointer is really a pointer, and there may be occurrences where a value is mistaken as an actual reference to allocated memory. Circular references that are no longer accessible from the program's variables also create an undetectable leak. For example, if a reference to allocated block x is placed in an allocated block y, and vice versa, and the program's references to x and y are lost, an undetectable leak is created.

Automating Checking

Checking for memory leaks and corrupted memory is triggered by a change to memList so that no function calls need to be added to existing source. Because the leak checking is relatively time consuming, it is executed automatically only if the time given by AUTOCHECK_PERIOD has elapsed since the last check. For debugging purposes, you can modify a program to explicitly call memtrackCheckPeriodic(int period), which checks for memory leaks if period seconds have elapsed since the last leak check and checks for corrupted end-of-block sentinels on each call.

Integration into a Project

To integrate the memtrack library into your project, you need to make the following definitions when the compiler is invoked:

-Dcalloc=MEMTRACK_CALLOC 
-Dmalloc=MEMTRACK_MALLOC
-Drealloc=MEMTRACK_REALLOC 
-Dvalloc=MEMTRACK_VALLOC
-Dfree=MEMTRACK_FREE 
-Dstrdup=MEMTRACK_STRDUP
-Dstrcat=MEMTRACK_STRCAT 
-Dstrcpy=MEMTRACK_STRCPY
Large projects typically have a central makefile that is included in all other makefiles. The central makefile usually contains compiler- and machine-specific flags and is the ideal place to put the definitions.

Each source file that contains any of the redefined routines needs to include memtrack.h. A large project typically has at least one header file of utility functions that is included almost everywhere. By adding memtrack.h to that header file, you will greatly reduce the number of source files you must edit.

You must also link in the object file produced by memtrack.c. If you have a library of utility functions that is common to most of your executables, then simply add memtrack.o to that library. For executables that do not use the library, you will have to edit their makefiles to link in the library. My experience has been that by appending the memtrack library to existing code in this way, minimal changes need to be made in a well-organized project.

During your linking, you might get a message such as Error: Undefined: MEMTRACK_MALLOC. This may be the result of memtrack.h missing from a particular source file. Find the source file by scanning through all the object files for the MEMTRACK text; go to the top of your build tree and execute the (Korn) shell script:

#!/usr/bin/ksh
for i in 'find . -name "*.o"'
do
    if [[ 'nm $i | grep MEMTRACK
         | wc -l' -ne 0 ]]
    then
        echo $i
    fi
done
This script will print out all the object files whose source files require memtrack.h. Edit the corresponding source files and rebuild.

The link will also fail if some of the functions to be redefined are actually passed as parameters. For example:

void f1(void* data,
        void(*freeFun)(void*)) {
    freeFun(data);
}
void f2(void) {
    f1(buf, free)
}
In this case, the function redefinition scheme will not work even with memtrack.h present. The solution is to create a proxy function with the same signature, as shown below:

static void myFree(void* buf) {
    free(buf);
}
void f2(void) {
    f1(buf, myFree)
}

Multithreading Issues

The memtrack library is POSIX thread safe. You can build it in multithreaded mode by defining MULTI_THREAD. In multithreaded mode, all access to memList is protected by a mutex declared in the mutexOp function, and the macros MUTEX_LOCK and MUTEX_RELEASE are defined to call that function. In a multithreaded program, each thread's stack is placed on the heap. At the end of each thread stack is a guard region designed to cause a segmentation violation when accessed. Unfortunately, I have not found a way to determine the start and end of all the guard regions, nor have I been able to deactivate them. Listing 2 shows code to scan through the heap portion of memory and my heavy-handed solution to the guard region problem. The code uses a signal handler in combination with setjmp/longjmp to push its way through the guard regions. Before the heap is scanned, the SET_SIGSEGV_ACTION macro sets the segvHandler function to be executed on a segmentation violation. The SETJMP macro issues a setjmp call, saves the current execution context, and returns 0. When the segvHandler is called, it executes a longjmp, bringing the program back to the point of the setjmp function call. However, now the setjmp returns 1, not 0, passing control to the outer loop and incrementing the scanPoint. In this way, the inaccessible regions are eventually passed and scanning can continue. After the heap scan, the original SIGSEGV action is restored with RESET_SIGSEGV_ACTION. In single-threaded mode, the macros SETJMP, MUTEX_LOCK, MUTEX_RELEASE, SET_SIGSEGV_ACTION, and RESET_SIGSEGV_ACTION are no-ops.

Conclusion

The techniques described here use some features of the preprocessor that may not be common knowledge. These features may require research into some esoteric aspects of Unix system programming. However, you'll find no tricky algorithms here. Once you know the conventions of how memory is laid out in your system, the operations are straightforward. Considering that, I have been both pleased and surprised at the effectiveness of this solution. I've integrated it into a 700-file, 500,000-line project (excluding header files) with ease. It has exposed many instances of memory leaks, memory overruns, usage of freed memory, and freeing of automatic variables. I have found this technique especially useful as an instructional tool for novices, but it has saved me from my own code on many occasions as well.

References

[1] W. Richard Stevens. Advanced Programming in the Unix Environment (Addison-Wesley, 1993), Chapter 7.

[2] Digital Unix Assembly Language Programmer's Guide (Digital Equipment Corporation, March 1996), Chapter 7.

About the Author

Zlatko Marcok has a BASc in Computer Engineering from the University of Waterloo, Canada. He has been developing software for 11 years and is currently on contract with Ontario Power Generation. Reach him at wmarcok@pathcom.com.