Detecting and Eliminating Memory Leaks Using Cyclic Memory Allocation
Huu Hai Nguyen and Martin Rinard
The 2007 International
Symposium on Memory Management (ISMM 2007) Montreal, Canada, 21-22
October, 2007
Abstract
We present and evaluate a new technique for detecting and
eliminating memory leaks in programs with dynamic memory allocation. This
technique observes the execution of the program on a sequence of training inputs
to find $m$-bounded allocation sites, which have the property that at any time
during the execution of the program, the program accesses at most only the last
$m$ objects allocated at that site. If the difference between the number of
allocated and deallocated objects at the site grows above $m$ throughout the
computation, there is a memory leak at that site. To eliminate the leak, the
technique transforms the program to use {\em cyclic memory allocation} at that
site: it preallocates a buffer containing $m$ objects of the type allocated at
that site, with each allocation returning the next object in the buffer. At the
end of the buffer the allocations wrap back around to the first object. Cyclic
allocation eliminates any memory leak at the allocation site --- the total
amount of memory required to hold all of the objects ever allocated at the site
is simply $m$ times the object size.
We evaluate our technique by applying it to several widely-used open source
programs. Our results show that it is able to successfully detect and eliminate
important memory leaks in these programs. A potential concern is that the
estimated bounds $m$ may be too small, causing the program to overlay live
objects in memory. Our results indicate that our bounds estimation technique is
quite accurate in practice, providing incorrect results for only one of the 160
$m$-bounded sites that it identifies. To evaluate the potential impact of
overlaying live objects, we artificially reduce the bounds at $m$-bounded sites
and observe the resulting behavior. The resulting overlaying of live objects
often does not affect the functionality of the program at all; even when it does
impair part of the functionality, the program does not fail and is still able to
acceptably deliver the remaining functionality.