More on Memory Leaks - Embedded.com

More on Memory Leaks

The best way to detect memory leaks is to use a smarter memory allocator. That turns out to be easier than you might think.

Last month, I discussed the challenges of tracking down memory leaks, and began to look at modifying our allocator function to provide us with extra information. This month, we will continue in that vein.

We use an array to keep a record of each block of allocated memory. When the block is freed, we remove that record from our array. After each iteration of the main loop, we print a summary of the number of allocated blocks. Ideally, we would sort these blocks by type, but calls to malloc() and free() do not contain any type information. The best indication available is the size of the allocations, so that's what we'll record. We also need to store the address of the block allocated, so that we can locate and remove the record for that block when free is called.

Listing 1 A smarter memory allocator

static BlockEntry blocks[NUM_BLOCKS];static Counter counters[NUM_SIZES];

static void incrementCountForSize(size_t size);static void decrementCountForSize(size_t size);

static long FS_totalAllocated = 0;

void *mMalloc(size_t size){ int i; void *newAllocation = malloc(size);

for (i = 0; i < NUM_BLOCKS; i++) { if (blocks[i].addr = = 0) { // found empty entry; use it blocks[i].addr = newAllocation; blocks[i].size = size; incrementCountForSize(size); break; } } assert(i < NUM_BLOCKS);

FS_totalAllocated += size; return newAllocation;}

void mFree(void *blockToFree){ int i; for (i = 0; i < NUM_BLOCKS; i++) { if (blocks[i].addr = = blockToFree) { // found block being released decrementCountForSize(blocks[i].size); FS_totalAllocated -= blocks[i].size; blocks[i].addr = 0; blocks[i].size = 0; break; } } assert(i < NUM_BLOCKS);

free(blockToFree);}

void mDisplayTable(void){ printf("%s", "nSizetFreq."); for (int i = 0; i < NUM_SIZES; i++) { if (counters[i].size = = 0) break; printf("n%dtt%d", counters[i].size, counters[i].count); }}

void mClearTable(void){ for (int i = 0; i < NUM_SIZES; i++) { counters[i].size = 0; counters[i].count = 0; }}

As we add and remove blocks, we also keep track of the number of blocks of each size. Listing 1 contains the code to do this. As blocks are allocated and freed, an array of:

typedef struct{	void * address;	size_t size;} BlockEntry;

keeps track of all blocks currently in existence. Another array of keeps track of the total number of blocks of each size in existence:

typedef struct{	int  count;	size_t  size;} Counter;

The mDisplayTable() function allows us to output the results at the end of each main loop. If printf() is not available, you can halt the system with a debugger and examine the contents of the array.

The code shown needs to be tuned to set NUM_SIZES and NUM_BLOCKS large enough to cope with the number of allocations in your system, but not so large that you use up all of your RAM before you begin.

The output

As a quick aside, we will look at the size of the Sensor structure. It is defined as:

typedef struct{	int offset;	int gain;	char name[10];} Sensor;

Assuming an int is 32 bits, a reasonable guess at the size of this structure would be 18 (4 + 4 + 10). However, running our test showed it to be 20. The compiler is free to add padding between data members of a structure in order to force the alignment to be on a word boundary. In this particular case, each field starts on a word boundary already, so why the padding? The padding is added at the end of the structure. If we declare an array of Sensor, all elements of the array (and not just the first) will be word aligned. Depending on the processor, word alignment may make a speed difference, and sometimes those compilers will provide a switch that trades size against speed. In any case, it is best to make no assumptions about the size of a structure from reading the definition in the source code.

Let's see what type of output we get when we use these functions. Listing 2 shows a contrived example that demonstrates some ways to store dynamic memory. Listing 2 runs 10 iterations of what would normally be the main outer loop. At the end of each iteration, we call mDisplay-Table() to output a summary of the blocks allocated.

Listing 2 Example application code

#include "mmalloc.h"int main(void){	char cbuf;

initialize(); mClearTable(); for (int i = 0; i < 10; i++) {

replacer(); growAndShrink(); growForever(); printf("n End of iteration %d", i); mDisplayTable(); } return 0;}

Sensor *replacePtr = NULL;void replacer(void){ if (replacePtr != NULL) mFree(replacePtr); replacePtr = mMalloc(sizeof(Sensor));}

MsgBuffer *manyBuffers[30];int numBuf = 0;void growAndShrink(void){ if (numBuf > 20) { for (int i = 0; i < 5; i++) { numBuf--; mFree(manyBuffers[numBuf]); manyBuffers[numBuf] = NULL; } } else { for (int i = 0; i < 5; i++) { manyBuffers[numBuf] = mMalloc(sizeof(MsgBuffer)); numBuf++; } }}

MsgBuffer *manyBadBuffers[200];int numBadBuf = 0;void growForever(void){ for (int i = 0; i< 5 ; i++) { manyBadBuffers[numBadBuf] = mMalloc(sizeof(BadBuffer)); numBadBuf++; }}

Many blocks are allocated during initialization. We aren't concerned with them because that code does not repeat, and, therefore, does not threaten a leak. Since we don't want to clutter our table with those allocations, we clear it just before we start the iterations that interest us. To clear the table, we call mClearTable() .

The main loop calls three different functions. Each one allocates memory in different ways.

The replacer() function shows a pointer that is used to allocate a block that is not freed until the following iteration of the loop. If we examine one iteration of the main loop, we see the block allocated and not freed. By monitoring the total number of blocks of size 20, we see, as shown in Table 1, that the total number of blocks at the end of each iteration is one. No leak has occurred.

Table 1 Allocated memory blocks by size
End of Iteration 0 End of Iteration 5
Size Frequency Size Frequency
20 1 1 1
24 5 5 20
44 5 5 30
End of Iteration 1 End of Iteration 6
Size Frequency Size Frequency
20 1 1 1
24 10 5 25
44 10 5 35
End of Iteration 2 End of Iteration 7
Size Frequency Size Frequency
20 1 1 1
24 15 5 20
44 15 540
End of Iteration 3 End of Iteration 8
Size Frequency Size Frequency
20 1 1 1
24 20 5 25
44 20 5 45
End of Iteration 4 End of Iteration 9
Size Frequency Size Frequency
20 1 1 1
24 25 5 20
44 25 5 50

The growAndShrink() function manages a linked list of size 24 structures that grows longer and shorter over time. But we don't want the list to grow indefinitely. Examining the number of blocks of size 24, we see that, while the number of blocks in existence at any one time varies, it does not exceed 25.

The growForever() function deals in blocks of size 44. Here we can see quite plainly that the number of blocks in existence keeps growing. When you first observe this in the table, you will not know the source. The first quick and dirty check you can perform is a conditional breakpoint on mMalloc() that only fires if the size parameter is 44. When you hit this breakpoint, examine the stack to see where the allocation took place. You should probably do this several times, since blocks of this size may be allocated in more than one place.

Strictly speaking, the memory consumed in growForever() is not a leak, because there are references to all blocks allocated and they could, theoretically, be freed later. It will usually be fairly obvious if a particular application is likely to do this.

Size as key

The preceding technique is less useful when many different types of objects share the same size. In practice, I have not found this much of an issue, but if it does cause problems, you have a couple of options.

A more sophisticated approach is to store type information in each record. This is not difficult, but I shy away from it because it requires adding something new to the signature of mMalloc() . We could define an enumerated type that lists all of the types that may be allocated. In each call to the mMalloc() function, an extra argument that was one of the elements of the enumerated typecould be passed. If this element were stored along with the address in our table, we could always identify the type of the object.

This would also allow us to link together allocations of different size, but related types, such as character arrays of varying length.

C++ facilitates this approach by allowing us to overload new and delete on a per-class basis.[1] While this is a useful path, I will not pursue it here; I would prefer to stick with techniques that can be used in a C environment.

Allocation location

Sometimes, location information is more useful than type information. Fortunately, we can pick up this information without changing our signature if we make some clever use of macro definitions:

#define mMalloc(size_t size)	mMallocLineNo(size, __LINE__,	__FILE__)

(My May 2001 column discusses the __LINE__ and __FILE__ macros, as well as some tricks to avoid the overhead from the __FILE__ string.[2])

Listing 3 Allocations can be tracked by line number

void *mMallocLineFile(size_t size, int line, char *file){	int i;	void *newAllocation = malloc(size);

for (i = 0; i < NUM_BLOCKS; i++) { if (blocks[i].addr == 0) { // found empty entry; use it blocks[i].addr = newAllocation; blocks[i].size = size; blocks[i].line = line; blocks[i].file = file; incrementCountForSize(size); break; } } assert(i < NUM_BLOCKS);

FS_totalAllocated += size; return newAllocation;}

The mMallocLineNo() function is a slight variation of the mMalloc() function from Listing 1. We now want to store line number and filename information as shown in Listing 3. To hold this extra information, our BlockEntry structure becomes:

typedef struct {	void * addr;	size_t size;	int  line;	char * file;} BlockEntry;

By storing the line number and file name for each block, we can know exactly where any block was allocated. I find it useful to add a function called mDisplayLocation() that outputs the line number and file name for all entries of a particular size. This makes it easy to identify the source of any blocks of the size that looks suspicious.

Returning to Table 1, we may worry about the blocks of size 44. To learn more about where this memory came from, we can put the following line at the end of main() :

mDisplayLocation(44);

This leads to the output of 50 copies of the line:

line = 162, file = listing2.c

This shows unambiguously that all allocated blocks were allocated within the growForever() function.

Varying sizes

The size of some allocations may vary greatly. For example:

char *p = malloc(strlen(name)+1);

is a common way to allocate a block of memory large enough to store a string name plus a string terminator. In embedded systems, string and file manipulation are uncommon; data structure allocations are not. For example:

Motor *m = malloc(sizeof(Motor));

If we assume Motor is a structure, this allocation will always result in a block of the same size. This makes it easier to identify these blocks in the output of the functions described above.

When allocations of varying sizes are a concern, the code can be modified to use the combination of line number and file name as the key for counting the number of allocations. In our examples, we stored the line number and filename, but the printed summaries were based on size. Using the line number and filename to group allocations would combine all allocations that occurred in the same place, regardless of size. In some cases, this analysis is more revealing even when varying sizes is not an issue.

Turn to the tables

Any code with a memory leak should cause the tables shown here to grow. Not all leaks will be identified as clearly or unambiguously as our growForever() example. Even if you use another technique for leak detection and removal, these output tables will help confirm whether a leak has been eliminated.

The loop shown here did not have varying input data. In real projects, I usually insert some calls to fake input, such as a call to simulate a sequence of keypresses. In your system, you will also have to create some suitable input. Unless you vary it, you may not visit the pieces of code that create the leak. For this reason, the examples shown here represent a good starting point for your hunt, but each leak is still likely to take some detective work. Happy hunting.

Niall Murphy has been writing software for user interfaces and medical systems for ten years. He is the author of Front Panel: Designing Software for Embedded User Interfaces. Murphy welcomes feedback and can be reached at . Reader feedback to this column can be found at .

References

1. Eckel, Bruce. Thinking in C++. Upper Saddle River, NJ: Prentice Hall, 2000.

Back

2. Murphy, Niall. “Assert Yourself,” Embedded Systems Programming , May 2001, p. 27.

Back

Return to the April Table of Contents

Leave a Reply

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