ISMM 2007 START Conference Manager    

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


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.

START Conference Manager (V2.54.5)